Source of ArrayMaxHeap.cpp


  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