Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
void pointer
Vector of pointer of P...
DESim Example with Hash Table
Tree Example
Non type template argument
Deleted special operations are propagated to derived class
user defined exception
GraphBase
Assignment Operator Example
Recursive Call Example Sum