Heap: insert and deleteMin() Implementations, C++ (clang)

Heap: insert and deleteMin() Implementations

// Array-Based Heap Example

#include <iostream>
#include <algorithm>
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;
    
    int index = itemCount; 
    bool done = false; 
    
    while((index > 1) && (!done)){
        
        if(items[index] < items[index/2]){
             swap(items[index], items[index/2]); 
             index = index/2; 
        }
        else{
            done = true; 
        }   
    }
}

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--;
    
    bool done = false; 
    int index = 1; 
    
    while((!done) && (index < itemCount)){
        
        int checkLeft = index * 2; 
        int checkRight = index *2 + 1; 
        
        if((checkLeft <= itemCount) && (checkRight <= itemCount)){
        
            if((items[index] > items[index*2]) && (items[index] > items[index*2 + 1])){
            
                if((items[index*2] < items[index*2 + 1])){
                    swap(items[index], items[index*2]);
                
                    index = index*2; 
                }
                else{
                    swap(items[index], items[index*2 + 1]); 
                    index = index*2 + 1; 
                }            
            }
            else{
                done = true; 
            }
        }
        else if((checkLeft <= itemCount) && (items[index] > items[checkLeft])){
            
            swap(items[index], items[checkLeft]); 
            index = checkLeft; 
        }
        else{
            done = true; 
        }       
    }
                
    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