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: