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 + 1 A [ A.heapsize] = -∞ Increase-key(A, A.heapsize, key) Priority queues Runtime? Maximum = Extract-Max = Increase-Key = Insert = Priority queues Runtime? Maximum = O(1) Extract-Max = O(lg n) Increase-Key = O(lg n) Insert = O(lg n) Priority queues Name 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=kPRA0W1kECg Sorting comparisons: