6.5 Priority queues¶

6.5-1¶

Suppose that the objects in a max-priority queue are just keys. Illustrate the operation of MAX-HEAP-EXTRACT-MAX on the heap $A <15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 >$.

MAX-HEAP-EXTRACT-MAX

6.5-2¶

Suppose that the objects in a max-priority queue are just keys. Illustrate the operation of MAX-HEAP-INSERT(A,10) on the heap $A < 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 >$.

MAX-HEAP-INSERT

6.5-3¶

Write pseudocode to implement a min-priority queue with a min-heap by writing the procedures MIN-HEAP-MINIMUM, MIN-HEAP-EXTRACT-MIN, MIN-HEAP-DECREASE-KEY, and MIN-HEAP-INSERT.

MIN-HEAP-MINIMUM(A)
    if A.heap-size < 1
        error "heap underflow"
    return A[1]

MIN-HEAP-EXTRACT-MIN(A)
    min = MIN-HEAP-MINIMUM(A)
    A[1] = A[A.heap-size]
    A.heap-size = A.heap-size - 1
    MIN-HEAPIFY(A,1)
    return min

MIN-HEAP-DECREASE-KEY(A,x,k)
    if k > x.key
        error "new key is larger than current key"
    x.key = k
    find the index i in array A where object x occurs
    while i > 1 and A[PARENT(i)].key > A[i].key
        exchange A[i] with A[PARENT(i)], updating the information that maps priority queue objects to array indices
        i = PARENT(i)

MIN-HEAP-INSERT(A,x,n)
    if A.heap-size == n
        error "heap overflow"
    A.heap-size = A.heap-size + 1
    k = x.key
    x.key = +∞
    A[A.heap-size] = x
    map x to index heap-size in the array
    MIN-HEAP-DECREASE-KEY(A,x,k)

6.5-4¶

Write pseudocode for the procedure MAX-HEAP-DECREASE-KEY(A,x,k) in a max-heap. What is the running time of your procedure?

MAX-HEAP-DECREASE-KEY(A,x,k)
    if k > x.key
        error "new key is larger than current key"
    x.key = k
    find index i in array A where objext x occurs
    MIN-HEAPIFY(A,i)

The running time of the procedure is $O(1)+O(\lg n) = O(\lg n)$.

6.5-5¶

Why does MAX-HEAP-INSERT bother setting the key of the inserted object to $- \infty$ in line 5 given that line 8 will set the object’s key to the desired value?

To reuse MAX-HEAP-INCREASE-KEY as a subprocedure for convenience, we must pass the guard clause if k > x.key.

6.5-6¶

Professor Uriah suggests replacing the while loop of lines 5-7 in MAX-HEAP-INCREASE-KEY by a call to MAX-HEAPIFY. Explain the flaw in the professor’s idea.

A call to MAX-HEAPIFY(A,i) may break the priority property of the max-heap rooted $A[PARENT(PARENT(i))]$. So we must use a while loop to repeatedly check whether $A[ i ] > A[PARENT(i)]$ and then exchange them.

6.5-7¶

Argue the correctness of MAX-HEAP-INCREASE-KEY using the following loop invariant:

At the start of each iteration of the while loop of lines 5-7:

a. If both nodes PAREBT(i) and LEFT(i) exist, then $A [ PARENT ( i ) ].key \geq A [ LEFT ( i ) ].key$.

b. If both nodes PARENT(i) and RIGHT(i) exist, then $A [ PARENT ( i ).key ] \geq A [RIGHT ( i ) ].key$.

c. The subarray $A[ 1 : A.heap\text{-}size ]$ satisfies the max-heap property, except that there may be one violation, which is that $A[i].key$ may be greater than $A[PARENT(i)].key$.

You may assume that the subarray $A[ 1 : A.heap\text{-}size ]$ satisfies the max-heap property at the time MAX-HEAP-INCREASE-KEY is called.

a.

Initialization: Since the subarray $A[ 1 : A.heap\text{-}size ]$ satisfies the max-heap property at the time MAX-HEAP-INCREASE-KEY is called, $A.key \geq A[i].key' \geq A [ LEFT ( i ) ].key$, while $A [ i ].key'$ donate the $key$ of $A[ i ]$ before MAX-HEAP-INCREASE-KEY is called.

Maintenance: In each iteration, if $A [ i ] \geq A[PARENT(i)]$:

case 1: $i = lEFT(PARENT(i))$, since $A[PARENT(PARENT(i))].key \geq A[PARENT(i)].key$, after we exchange $A[i]$ with its parent, $A[PARENT(i)] \geq A[LEFT(i)]$.

case 2: $i = RIGHT(PARENT(i))$, $A[PARENT(PARENT(i))].key \geq A[LEFT(PARENT(i))].key$, after we exchange $A[i]$ with its parent, $A[PARENT(i)] \geq A[LEFT(i)]$.

Termination: The loop terminates whenever the heap is exhausted or $A[i] \leq A[PARENT(i)]$. Since during the last iteration, $A[PARENT(i)] \geq A[LEFT(i)]$ holds, it holds at Termination.

b.

The same as a, the only thing need to do is exchange $LEFT$ and $RIGHT$.

c.

Initialization: Since the subarray $A[ 1 : A.heap\text{-}size ]$ satisfies the max-heap property at the time MAX-HEAP-INCREASE-KEY is called, $A [ PARENT ( i ) ].key \geq A[i].key' \geq A [ LEFT ( i ) ].key$, while $A [ i ].key'$ donate the $key$ of $A[ i ]$ before MAX-HEAP-INCREASE-KEY is called. Because others' keys are unchanged, so the subarray $A[ 1 : A.heap\text{-}size ]$ satisfies the max-heap property, except that there may be one violation, which is that $A[i].key$ may be greater than $A[PARENT(i)].key$.

Maintenance: In each iteration, if $A [ i ] \geq A[PARENT(i)]$, since $A[PARENT(i)] \geq A[LEFT(i)]$ and $A[PARENT(i)] \geq A[RIGHT(i)]$, after we exhange them and update $i$, the loop invariant holds.

Termination: The loop terminates whenever the heap is exhausted or $A[i] \leq A[PARENT(i)]$. Since during the last iteration, the loop invariant holds, it holds at Termination.

6.5-8¶

Each exchange operation on line 6 of MAX-HEAP-INCREASE-KEY typically requires three assignments, not counting the updating of the mapping from objects to array indices. Show how to use the idea of the inner loop of INSERTION-SORT to reduce the three assignments to just one assignment.

MAX-HEAP-INCREASE-KEY(A,x,k)
    if k < x.key
        error "new key is larger than current key"
    x.key = k
    tmp = A[i]
    find the index i in array A where object x occurs
    while i > 1 and A[PARENT(i)].key > tmp.key
        A[i] = A[PARENT(i)]
        updating the information that maps priority queue objects to array indices
        i = PARENT(i)
    A[i] = tmp

6.5-9¶

Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue. (Queues and stacks are defined in Section 10.1.3.)

First-in, first-out queue: Insert the element in decreasing priority. For instance, we can set new piority as MIN-QUEUE-PRIORITY()-1.

Stack: Insert the element in increasing priority. For instance, we can set new piority as MAX-STACK-PRIORITY()+1.

However, there is a question that the priority can overflow or underflow. Each time it occurs, the procedure should reassign the priorities.

6.5-10¶

The operation MAX-HEAP-DELETE(A,x) deletes the object $x$ from max-heap $A$. Give an implementation of MAX-HEAP-DELETE for an $n$-element max-heap that runs in $O(\lg n)$ time plus the overhead for mapping priority queue objects to array indices.

MAX-HEAP-DELETE(A,x)
    find the index i in array A where x occurs
    if A[i].key > A[A.heap-size].key
        MAX-HEAP-DECREASE-KEY(A , x , A[A.heap-size].key)
    else
        MAX-HEAP-INCREASE-KEY(A , x , A[A.heap-size].key)
    A.heap-size = A.heap-size - 1

6.5-11¶

Give an $O(n \lg k)$-time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a minheap for $k$-way merging.)

MERGE-SORTED-LIST(k,lists)
    l = list.length
    Let A be an empty array of pairs of pointer and key
    for i = 1 to l
        A[i].pointer = lists[i]
        A[i].key = lists[i][1] 
    BUILD-MIN-HEAP(A,k)
    i = 1
    Let merge-lists be an empty array
    while A.heap-size > = 1// n iterations
        L = MIN-HEAP-MINIMUM(A)
        merge-lists[ i ] =  L.key
        /*
        assume that the elements of the list is in Continuous address

        assume that L is the refference of A[1], that is L.pointer = L.pointer + 1 is the same as A[1].pointer = A[1].pointer + 1
        */
        L.pointer = L.pointer + 1
        //check whether L.pointer is out-of-bounds
        if L.pointer
            newkey = *(L.pointer)// "*p" denate the element of the address stored in p
            MIN-HEAP-INCREASE-HEAP(A,L,newkey)//O(lg k)
        else
            MIN-HEAP-EXTRACT-MIN(A)