#include #include #include //#include #include "heap.h" Binheap::Binheap(int totCap) { elements = new int[totCap+1]; // we start the indexing at #1 size = 0; capacity = totCap; elements[0] = INT_MIN; // key cannot be smaller than INT_MIN } void Binheap::insert(int x) { if ( isFull() ) { cout << "Heap is full"< key) { // slide the parent down. elements[i] = elements[i/2]; i = i/2; } // At last, our key is smaller, so we can insert // the element at this location. elements[i] = key; } void Binheap::percolateDown(int i) { // Uses the same method of "sliding" as described // in "percolateUp". int child; int key = elements[i]; while (i*2 <= size) { // Stop if node has no children. // Find smallest child. child = i*2; if (child != size && elements[child+1] < elements[child]) // The right child exists and is smaller than the left child child++; /// Percolate one level if (key > elements[child]) elements[i] = elements[child]; else break; // Follow path to smallest child and test again. i = child; } // Finally, insert the new key elements[i] = key; } void Binheap::changeKey(int i, int key) { if (i < 1) return; if (i > size) return; if (key > elements[i]) { elements[i] = key; percolateDown(i); } else { elements[i] = key; percolateUp(i); } } void main() { Binheap *bh = new Binheap(100); int i; // randomize(); for (i=0; i<20; i++) bh->insert(rand()); bh->printHeap(); /* for (i=0; i<100; i++) bh->changeKey(i+1, rand()); for (i=0; i<20 ; i++) cout << bh->deleteMin() << endl;*/ }