// index-heap-based priority queue. heap routines are // from "Algorithms in C, Third Edition", and // "Algorithms in Java, Third Edition", Robert Sedgewick // Summer 2016, changed for CLRS, 3rd ed., but still non-recursive. // This is a prototype for demonstration purposes only. #include #include typedef int Item; int N, // Number of items in queue *pq, // Priority queue *qp, // Table of handles (for tracking) maxQueued; // Capacity of priority queue int *a; int parent(int i) { return i/2; } int left(int i) { return 2*i; } int right(int i) { return 2*i+1; } void exch(int i, int j) { // Swaps parent with child in heap int t; t = pq[i]; pq[i] = pq[j]; pq[j] = t; qp[pq[i]] = i; qp[pq[j]] = j; } void maxHeapInit(int *items,int n,int m) { int i; a = items; // Save reference to index table maxQueued=m; N = 0; pq=(int*) malloc((maxQueued+1)*sizeof(int)); // Contains subscripts to a[] if (!pq) { printf("malloc failed %d\n",__LINE__); exit(0); } qp=(int*) malloc(n*sizeof(int)); // Inverse of pq, allows changing priorities if (!qp) { printf("malloc failed %d\n",__LINE__); exit(0); } // Set all handles to unused for (i=0;i 1 && less(parent(k), k)) { exch(k, parent(k)); k = parent(k); } } void maxHeapify(int *pq,int k, int N) // AKA sink { int j; while (left(k) <= N) { j = left(k); if (j < N && less(j, j+1)) j=right(k); if (!less(k, j)) break; exch(k, j); k = j; } } void maxHeapInsert(int k) { qp[k] = ++N; pq[N] = k; heapIncreaseKey(pq, N); } int heapExtractMax() { exch(1, N); maxHeapify(pq, 1, --N); qp[pq[N+1]]=(-1); // Set to unused return pq[N+1]; } void maxHeapChange(int k) { // To be called when priority[k] has changed. heapIncreaseKey(pq, qp[k]); maxHeapify(pq, qp[k], N); } // Test driver for index-heap-based priority queue. // Index is just a table of priorities whose // subscripts are used in the PQ. int main() { int n,m,op,i,val; int *priority; printf("Enter table (dictionary) size\n"); scanf("%d",&n); if (n<1) { printf("Illegal size %d\n",__LINE__); exit(0); } priority=(int*) malloc(n*sizeof(int)); if (!priority) { printf("malloc failed for table %d\n",__LINE__); exit(0); } printf("Your table has keys %d through %d\n",0,n-1); printf("Enter PQ (binary heap) size\n"); scanf("%d",&m); maxHeapInit(priority,n,m); for (i=0;i%d for heapExtractMax)\n",n-1); scanf("%d",&op); if (op<0) break; if (op>=n) if (maxHeapEmpty()) printf("Can't do heapExtractMax() when pq is empty\n"); else { i=heapExtractMax(); printf("heapExtractMax() indicates priority[%d]=%d\n",i, priority[i]); priority[i]=(-1); } else { if (priority[op]<0) { if (maxHeapFull()) printf("pq already full\n"); else { val=(-1); while (val<0) { printf("Enter non-negative priority to maxHeapInsert() at table slot %d\n", op); scanf("%d", &val); } priority[op]=val; maxHeapInsert(op); } } else { val=(-1); while (val<0) { printf("Enter non-negative priority for maxHeapChange() of table slot %d\n", op); scanf("%d",&val); } priority[op]=val; maxHeapChange(op); } } } free(priority); free(pq); free(qp); }