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