Array-Based Heap Example Starter Code, C++ (clang)

Array-Based Heap Example Starter Code

// 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;
}

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--;
    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