// Binary heap routines - root (at subscript 1) has minimum. // Also supports handle array for linking from another data structure. // handle[i] gives the heap subscript for the entry with // id number i. (Also, handle[heap[j].id]==j . . .). #include #include #include "minHeap.h" using namespace std; bool minHeap::full() // Is this heap full? { return n==maxSub; } bool minHeap::empty() // Is this heap empty? { return n==0; } void minHeap::heapify(int j) { // The subtrees to the left and right of heap[j] must have // the minHeap property. At completion of this routine, the // entire subtree rooted at heap[j] will have the minHeap // property. int best,r; heapEntryType entry=heap[j]; while (1) { // Find child with smaller priority best=LEFT(j); if (best>n) break; // Gone past the leaves r=RIGHT(j); // Does left or right child have the smaller priority? if (r<=n && heap[best].priority>heap[r].priority) best=r; if (entry.priority<=heap[best].priority) break; // minHeap property holds in subtree // Move best child to parent heap[j]=heap[best]; handle[heap[j].id]=j; // Continue rippling one level deeper. // Again, the left and right subtrees have the minHeap property. j=best; } // Drop off item from root of subtree (original j) heap[j]=entry; handle[heap[j].id]=j; } void minHeap::swapUp(int j) { // Ancestors of heap[j] have the minHeap property, // so fixing the heap is a matter of having heap[j] // climb past its ancestors with larger priorities. int p; heapEntryType entry=heap[j]; p=PARENT(j); while (p>=1 && heap[p].priority>entry.priority) { heap[j]=heap[p]; handle[heap[j].id]=j; j=p; p=PARENT(j); } // Drop off item with new priority heap[j]=entry; handle[heap[j].id]=j; } int minHeap::getPriority(int id) { if (id<0 || id>=maxSub || handle[id]==(-1)) { cout << "id " << id << " issue for getPriority " << __LINE__ << "\n"; exit(0); } return heap[handle[id]].priority; } void minHeap::changePriority(heapEntryType iEntry) { // Changes priority of item iId to iPriority int i=handle[iEntry.id]; if (iEntry.priority>heap[i].priority) { // New priority is larger, so slide down heap[i].priority=iEntry.priority; heapify(i); } else { // New priority is smaller, so swap up heap[i].priority=iEntry.priority; swapUp(i); } } void minHeap::insert(heapEntryType iEntry) // Insert a new heap entry. { int j; if (full()) { cout << "Heap table size exceeded!"<< __LINE__ << "\n"; exit(0); } if (iEntry.id<0 || iEntry.id>=maxSub || handle[iEntry.id]!=(-1)) { cout << "id " << iEntry.id << " issue for insert " << __LINE__ << "\n"; exit(0); } j=(++n); // Put next item into use // Swap the new item up the heap heap[j]=iEntry; swapUp(j); } void minHeap::deleteId(int id) // Deletes the entry for id and frees its handle. { heapEntryType work; int heapSlot,donor; if (id<0 || id>=maxSub || handle[id]==(-1)) { cout << "id " << id << " issue for delete " << __LINE__ << "\n"; exit(0); } heapSlot=handle[id]; handle[id]=(-1); donor=(n--); // Last leaf element gets moved if (donor==heapSlot) return; // Next two lines transform the donation into a change of priority. heap[heapSlot].id=heap[donor].id; handle[heap[heapSlot].id]=heapSlot; changePriority(heap[donor]); } heapEntryType minHeap::minimum() // Returns minimum element, but leaves it in the heap. { if (empty()) { cout << "Heap empty!"<< __LINE__ << "\n"; exit(0); } return heap[1]; } heapEntryType minHeap::extractMin() { heapEntryType returnEntry; if (empty()) { cout << "Heap empty!"<< __LINE__ << "\n"; exit(0); } // Values being returned returnEntry=heap[1]; handle[heap[1].id]=(-1); // Invalidate handle n--; // Item is taken out of use if (empty()) return returnEntry; // Last item (at highest-subscripted leaf) becomes the root and slides down. heap[1]=heap[n+1]; heapify(1); return returnEntry; } minHeap::minHeap(int capacity) { heap=new heapEntryType[capacity+1]; handle=new int[capacity]; if (!heap || !handle) { cout << "new failed!"<< __LINE__ << "\n"; exit(0); } // Invalidate handles for (int i=0;i0;i--) heapify(i); } minHeap::minHeap() { minHeap(50); } minHeap::~minHeap() { delete [] heap; delete [] handle; }