Array-Based Heap Example Solution, C++ (clang)

Array-Based Heap Example Solution

// Array-Based Heap Example

#include <iostream>
using namespace std;

#define INIT_SIZE 2
#define COMPARE <

template<class ItemType>
class Heap
{
private:
   ItemType  *items; // Array to hold items
   int itemCount; // Number of items in heap
   int maxItems; // The maximum number of items that can be stored in the heap
public:
    Heap() {items = new ItemType[INIT_SIZE+1]; itemCount = 0; maxItems = INIT_SIZE;};
    int size() const {return itemCount;};
    void insert(ItemType value);
    ItemType deleteMin();
}; // end Heap

template<class ItemType>
void Heap<ItemType>::insert(ItemType value)
{
    // check if we need more space for items
    if (itemCount == maxItems) { 
        ItemType *temp = new ItemType[2*maxItems+1];
        memcpy(temp,items,(maxItems+1)*sizeof(ItemType));
        maxItems *= 2;
        delete [] items;
        items = temp;
    }
    // add new item to last position in the binary tree
    itemCount++;
    items[itemCount] = value;
    // percolate the smaller item up the tree until
    // swapping stops, or we reach the root
    for (int pos = itemCount; pos > 1; pos = pos/2) {
        int parentIndex = pos/2;
        if (items[pos] COMPARE items[parentIndex]) { // compare value with parent
            swap(items[parentIndex],items[pos]);
        } else { // we have restored heap ordering, so we can exit
            return;
        }
    }
}

template<class ItemType>
ItemType Heap<ItemType>::deleteMin()
{
    // save the top of the heap for return
    ItemType returnValue = items[1];
    // move the last item in the array to the vacated root
    items[1] = items[itemCount];
    itemCount--;
    // percolate the larger items down the tree until
    // swapping stops, or we reach a leaf
    int pos = 1;
    bool done = false;
    while (!done) {
        int leftChildIndex = 2*pos;
        int rightChildIndex = 2*pos + 1;
        if (leftChildIndex > itemCount) { // check if we are at a leaf
            done = true;
        } else { // if not, see if we need to swap with one of the children
            int minIndex = pos; // keep track of extreme value and index
            ItemType minValue = items[pos];
            if (items[leftChildIndex] COMPARE minValue) { // left child
                minIndex = leftChildIndex;
                minValue = items[leftChildIndex];
            }
            if (rightChildIndex <= itemCount) { // right child might not exist!
                if (items[rightChildIndex] COMPARE minValue) { // right child
                    minIndex = rightChildIndex;
                    minValue = items[rightChildIndex];
                }
            }
            if (minIndex == pos) { // if heap ordered (no swap), we are done
                done = true;
            } else { // otherwise, swap the values and continue percolating down
                swap(items[pos],items[minIndex]);
                pos = minIndex;
            }
        }
    }
    return returnValue;
}

int main()
{
    cout << "*** Array-Based Heap Program for ECE 2574 ***\n\n";
    int testSize = 10;

// set root and search tree
    Heap<int> h;
    
    // add nodes using insert
    srand(12321);
    for (int i = 0; i < testSize; i++) 
    {
        int value = rand()%100;
        h.insert(value);
        cout << "Inserted " << value << " into heap." << endl;
    }
    cout << endl;
    
    for (int i = 0; i < testSize; i++) 
    {
        int value = h.deleteMin();
        cout << "Returned " << value << " from heap." << endl;
    }
    cout << endl;
    
    return 0;
}


run \| edit \| history \| help	0