Chapter 6 - Priority Queue

Document last modified:

Overview

Max heaps maintain the maximum heap value at array location 1.

A priority queue requires that the priority value be accessible at the head of the queue, location 1.

Example - The highest priority (max value) is array location 1.

Question 6.8

Suggest an algorithm for deleting the value at the head of the queue, the value at array location 1.

Is the max heap property maintained?

What is the estimated O run time?

Priority Queue

a queue that orders its elements based on a key value
it is not ordered by first come, first served (FIFO) method of a traditional queue
priority queues are normally ordered in one of two ways:
- largest key value is at the front of the queue (max heap)
- smallest key value is at the front of the queue (min heap)
the Corman book refers to the collection of elements as a set with the following operations to manipulate the queue
- Insert (S, x) - inserts element x into set S
- Maximum (S) - returns a copy of the key value that has the largest value in the priority queue
- Extract_Max (S) - removes and returns the key value that is the largest
- Increase_Key (S, x, k) - increases the value of the key located at position x in the queue; k is required to be greater than the key already stored at location x
A Max Heap (or Min Heap) can be used to implement a priority queue.

Heap_Maximum (A) -- preserves A -- pre: A satisfies the max heap property and heapsize[A] > 0 -- post: returns copy of key value at location 1
1	return A[1]

Max_Heap_Insert (A, key) -- alters A -- pre: A satisfies the max heap property -- post: key is added to A and A satisfies the max heap property
1	A.heapsize ← A.heapsize + 1
2	A[A.heapsize] ← -∞
3	Heap_Increase_Key (A, A.heapsize, key)

Heap_Increase_Key (A, i, key) -- alters A -- pre: key > A[i] and A.heapsize > 0 and -- A satisfies the max heap property -- post: there exists a k such that A[k] = key and -- A satisfies the max heap property
1	if key < A[i] then
2	error "new key is smaller than current key"
3	A[i] ← key
4	while i > 1 and A[Parent(i)] < A[i] do
5	exchange A[i] ↔ A[Parent(i)]
6	i ← Parent(i)

Heap_Extract_Max (A) -- alters A -- pre: A.heapsize > 0 and -- A satisfies the max heap property -- post: A[1] is removed and returned and -- A satisfies the max heap property
1	if A.heapsize < 1 then
2	error "heap underflow"
3	max ← A[1]
4	A[1] = A[ A.heapsize ]
5	A.heapsize ← A.heapsize - 1
6	Max_Heapify (A, 1)
7	return max

Heap_Increase_Key (A, i=9, key=15)

1	if key < A[i] then
2	error "new key is smaller than current key"
3	A[i] ← key
4	while i > 1 and A[Parent(i)] < A[i] do
5	exchange A[i] ↔ A[Parent(i)]
6	i ← Parent(i)

Question 6.9

Trace the effect of Heap_Increase_Key (A, i=7, key=20).

Trace the effect of Heap_Increase_Key (A, i=2, key=6). Why is this result necessary?

What is the estimated worst case run time order? the best?

Max_Heap_Insert (A, key=10)

1	A.heapsize ← A.heapsize + 1
2	A[ A.heapsize ] ← -∞
3	Heap_Increase_Key (A, A.heapsize, key)

Heap_Increase_Key (A, i, key)

1	if key < A[i] then
2	error "new key is smaller than current key"
3	A[i] ← key
4	while i > 1 and A[Parent(i)] < A[i] do
5	exchange A[i] ↔ A[Parent(i)]
6	i ← Parent(i)

Question 6.10

What is the array before and after insertion?

What is the worst case run time order?

Is the Line 2, A[A.heapsize] ← -∞, necessary?

Heap_Extract_Max (A)
1	if A.heapsize < 1 then
2	error "heap underflow"
3	max ← A[1]
4	A[1] = A[ A.heapsize ]
5	A.heapsize ← A.heapsize - 1
6	Max_Heapify (A, 1)
7	return max

Question 6.11

What is the worst case run time order?

Question 6.12

Give an O(lg n) algorithm to delete node i of A.
The following seems to work.

static void Max_Heap_Delete(int A[], int i) {
     exchange(A, heapsize, i);
     heapsize--;
     Max_Heapify(A, i);
}

But note what occurs on the following tree when Max_Heap_Delete(A, 5) runs to delete the 9.



Thanks to Gregory and Scott Reinhardt for pointing out the problem.

Question 6.13

Think about an O(lg n) algorithm to replace node i of A. Example: Replace node 9 with 23. Heap_Replace(A, 9, 23)

What are some of the problems? Consider replacing node 2 with 6: Heap_Replace(A, 2, 6)

What is one obvious solution?

Question 6.13

Max_Heapify is O(lg n), what is the lower bound Ω and when does it occur?

Max-Heapify (A, i)

1 l ← Left (i)

2 r ← Right (i)

3 if l ≤ A.heap-size and A[l] > A[i]

4    then largest ← l

5    else largest ← i

6 if r ≤ A.heap-size and A[r] > A[largest]

7    then largest ← r

8 if largest ≠ i then

9    exchange A[i] ↔ A[largest]

10    Max-Heapify (A, largest)

Max-Heapify (A, i)
1	l ← Left (i)
2	r ← Right (i)
3	if l ≤ A.heap-size and A[l] > A[i]
4	then largest ← l
5	else largest ← i
6	if r ≤ A.heap-size and A[r] > A[largest]
7	then largest ← r
8	if largest ≠ i then
9	exchange A[i] ↔ A[largest]
10	Max-Heapify (A, largest)