class ArrayMaxHeap
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: Listing 17-2.
6: @file ArrayMaxHeap.h */
7:
8: #ifndef _ARRAY_MAX_HEAP
9: #define _ARRAY_MAX_HEAP
11: #include "HeapInterface.h"
12: #include "PrecondViolatedExcep.h"
14: template<class ItemType>
15: class ArrayMaxHeap : public HeapInterface<ItemType>
16: {
17: private:
18: static const int ROOT_INDEX = 0; // Helps with readability
19: static const int DEFAULT_CAPACITY = 21; // Small capacity to test for a full heap
20: ItemType* items; // Array of heap items
21: int itemCount; // Current count of heap items
22: int maxItems; // Maximum capacity of the heap
23:
24: // ---------------------------------------------------------------------
25: // Most of the private utility methods use an array index as a parameter
26: // and in calculations. This should be safe, even though the array is an
27: // implementation detail, since the methods are private.
28: // ---------------------------------------------------------------------
29:
30: // Returns the array index of the left child (if it exists).
31: int getLeftChildIndex(const int nodeIndex) const;
32:
33: // Returns the array index of the right child (if it exists).
34: int getRightChildIndex(int nodeIndex) const;
35:
36: // Returns the array index of the parent node.
37: int getParentIndex(int nodeIndex) const;
38:
39: // Tests whether this node is a leaf.
40: bool isLeaf(int nodeIndex) const;
41:
42: // Converts a semiheap to a heap.
43: void heapRebuild(int subTreeRootIndex);
44:
45: // Creates a heap from an unordered array.
46: void heapCreate();
47:
48: public:
49: ArrayMaxHeap();
50: ArrayMaxHeap(const ItemType someArray[], const int arraySize);
51: virtual ~ArrayMaxHeap();
52:
53: // HeapInterface Public Methods:
54: bool isEmpty() const;
55: int getNumberOfNodes() const;
56: int getHeight() const;
57: ItemType peekTop() const throw(PrecondViolatedExcep);
58: bool add(const ItemType& newData);
59: bool remove();
60: void clear();
61: }; // end ArrayMaxHeap
62: #include "ArrayMaxHeap.cpp"
63: #endif