6.5 - Priority Queues
Application of a heap: Efficient Priority Queue
Priority Queues use in:
- Shortest-path
- Dijkstra's algo
- Heapsort
- Reverse order sorting
Priority Queues have 2 Forms:
- Max-PQ
- Min-PQ
Default? is max-PQ which is based on a max-heap
Priority Queue: maintains set of elts, each with a key
Max-PQ supports:
Insert(S, x) //ENQUEUE: like push
Maximum(S) // like top
Extract-Max(S) // DEQUEUE: like pop, extracts the highest priority item
Increase-Key(S,x,k) // like updateElt, increases priority of an item
Min-PQ supports:
Insert
Minimum
Extract-Min
Decrease-Key
We can use heaps to implement PQs
In practice, a handle is needed for each heap object, such as a pointer, and a handle for each heap elt, such as an array index
Heap-Maximum(A) in Max-PQ O(1)
Access extreme element
return A[1] // Ø(1) time
Heap_Extract-Max(A) O(log n)
Remove max element, reorganize heap
# NOTE: heap-size or heap_size is a word, not a subtraction in this case (CLRS)
if A.heap-size < 1
error "heap underflow"
max = A[1]
A[1] = A[A.heap-size]
A.heap-size = A.heap-size - 1
Max_Heapify(A, 1) // O(log n)
return max
Heap_Increase-Key(A, i, key) O(log n)
Update an element, reorganize heap
if key < A[i]
error " "
A[i] = key
while i > 1 and A[PARENT(i)] < A[i]
exchange A[i] with A[PARENT(i)]
i = PARENT(i)
Max_Heap-Insert(A, key) O(log n)
Insert an element, reorganize heap
A.heap_size = A.heap_size + 1
A[A.heap_size] = -inf
Heap-Increase-Key(A, A.heap-size, key)
10.1 - Stacks and Queues
We can represent dynamic sets by simple data structures that use pointers (arrays, linked lists)
- Stacks and Queues are dynamic sets
Stack: elt deleted from set is the one most recently inserted: Last-in, First-out, LIFO
Queue: elt deleted is always the one that has been in the set for the longest time, First-in, First-Out, FIFO
Stacks: PUSH, POP
Stack implemented as an array:
- S.top provides the index to the most recently inserted elt, if S.top is 0, stack is empty
...
Queues: ENQUEUE, DEQUEUE
- Queue has a head and a tail
Enqueue places an elt at the tail of the queue
Dequeue takes off the elt at the head of the queue