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