1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: /** Array-based implementation of the ADT heap.
5: @file ArrayMaxHeap.cpp */
7: // PARTIALLY COMPLETE
8:
9: #include "ArrayMaxHeap.h"
10: #include "PrecondViolatedExcep.h"
12: template<class ItemType>
13: int ArrayMaxHeap<ItemType>::getLeftChildIndex(const int nodeIndex) const
14: {
15: return (2 * nodeIndex) + 1;
16: } // end getLeftChildIndex
18: template<class ItemType>
19: void ArrayMaxHeap<ItemType>::heapCreate()
20: {
21: for (int index = itemCount / 2; index >= 0; index--)
22: {
23: heapRebuild(index);
24: } // end for
25: } // end heapCreate
27: template<class ItemType>
28: ArrayMaxHeap<ItemType>::
29: ArrayMaxHeap(const ItemType someArray[], const int arraySize):
30: itemCount(arraySize), maxItems(2 * arraySize)
31: {
32: // Allocate the array
33: items = new ItemType[2 * arraySize];
34:
35: // Copy given values into the array
36: for (int i = 0; i < itemCount; i++)
37: items[i] = someArray[i];
38:
39: // Reorganize the array into a heap
40: heapCreate();
41: } // end constructor
43: template<class ItemType>
44: ItemType ArrayMaxHeap<ItemType>::peekTop() const throw(PrecondViolatedExcep)
45: {
46: if (isEmpty())
47: throw PrecondViolatedExcep("Attempted peek into an empty heap.");
48:
49: return items[0];
50: } // end peekTop