Priority Queue, Min Heap

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111

#include <stdio.h> #define SZ 100 int heap[SZ]; int lastIdx = 0; // returns the index of a smaller child of the node 'idx' int whoIsSmaller(int idx) { int leftIdx = 2 * idx; int rightIdx = leftIdx + 1; if (rightIdx > lastIdx) { return leftIdx; } if (heap[leftIdx] < heap[rightIdx]) { return leftIdx; } else { return rightIdx; } } int dequeFromPQ() { if (lastIdx < 1) { return -999; } int retVal = heap[1]; heap[1] = heap[lastIdx]; lastIdx--; int myIdx = 1; while (1) { int leftIdx = 2 * myIdx; int rightIdx = leftIdx + 1; if (leftIdx > lastIdx) // no child { break; } int sIdx = whoIsSmaller(myIdx); if (heap[myIdx] < heap[sIdx]) { break; } else { int temp = heap[sIdx]; heap[sIdx] = heap[myIdx]; heap[myIdx] = temp; myIdx = sIdx; } } return retVal; } void enqueToPQ(int v) { lastIdx++; heap[lastIdx] = v; int myIdx = lastIdx; int pIdx = myIdx / 2; while(1) { if (pIdx < 1) { return; } if (heap[myIdx] > heap[pIdx]) { return; } int temp = heap[myIdx]; heap[myIdx] = heap[pIdx]; heap[pIdx] = temp; myIdx = pIdx; pIdx = myIdx / 2; } } int main(void) { enqueToPQ(5); // enqueue to Priority Queue enqueToPQ(4); // enqueue to Priority Queue enqueToPQ(3); // enqueue to Priority Queue enqueToPQ(2); // enqueue to Priority Queue enqueToPQ(1); // enqueue to Priority Queue //printf("%d %d %d\n", heap[1], heap[2], heap[3]); printf("%d\n", dequeFromPQ()); // should print '1' printf("%d\n", dequeFromPQ()); // should print '2' printf("%d\n", dequeFromPQ()); // should print '3' printf("%d\n", dequeFromPQ()); // should print '4' printf("%d\n", dequeFromPQ()); // should print '5' printf("%d\n", dequeFromPQ()); // should print '-999' return 0; }