[SOLVED] CS Heaps as queues

Heaps as queues

Heaps can also be used to implement priority queues (i.e. airplane boarding lines)
Operations supported are: Insert, Maximum, Extract-Max and Increase-key
Priority queues

Maximum(A): return A[ 1 ]
Extract-Max(A):
max = A[1]
A[1] = A[heapsize]
A.heapsize = A.heapsize 1 Max-Heapify(A, 1), return max
Priority queues

Increase-key(A, i, key):
A[ i ] = key
while ( i>1 and A [floor(i/2)] < A[i]swap A[ i ], A [floor(i/2)] i = floor(i/2)Opposite of Max-Heapify… move high keys up instead of low down Priority queues)Insert(A, key):A.heapsize = A.heapsize + 1A [ A.heapsize] = – Increase-key(A, A.heapsize, key) Priority queuesRuntime?Maximum = Extract-Max = Increase-Key = Insert = Priority queuesRuntime?Maximum = O(1) Extract-Max = O(lg n) Increase-Key = O(lg n) Insert = O(lg n) Priority queuesName Average Worst-case Insertion[s,i] Merge[s,p] Heap[i] Quick[~i,p] Counting[s] Radix[s] Bucket[s,p]O(n2)O(n lg n) O(n lg n) O(n lg n) O(n + k) O(d(n+k)) O(n)O(n2)O(n lg n)O(n lg n) O(n2)O(n + k)O(d(n+k)) O(n2)Sorting comparisons: https://www.youtube.com/watch?v=kPRA0W1kECgSorting comparisons: