Chapter 6.5

   (15 (13 (5 (4) (0)) (12 (6) (2))) (9 (8 (1)) (7)))
-> (1 (13 (5 (4) (0)) (12 (6) (2))) (9 (8) (7)))       # extract 15
-> (13 (12 (5 (4) (0)) (6 (1) (2))) (9 (8) (7))

   (15 (13 (5 (4) (0)) (12 (6) (2))) (9 (8 (1)) (7)))
-> (15 (13 (5 (4) (0)) (12 (6) (2))) (9 (8 (1) (*10*)) (7)))
-> (15 (13 (5 (4) (0)) (12 (6) (2))) (9 (*10* (1) (8)) (7)))
-> (15 (13 (5 (4) (0)) (12 (6) (2))) (*10* (9 (1) (8)) (7)))
-> (15 (13 (5 (4) (0)) (12 (6) (2))) (10 (9 (1) (8)) (7)))

HEAP-MINIMUM(A)
    return A[1]

HEAP-EXTRACT-MIN(A)
    if A.heapsize < 1
        error "heap underflow"
    min = A[1]
    A[1] = A[A.heapsize]
    A.heapsize = A.heapsize - 1
    MIN-HEAPIFY(A, 1)
    return min

HEAP-DECREASE-KEY(A, i, key)
    if key > A[i]
        error "new key is larger than current key"
    A[i] = key
    while i > 1 and A[PARENT(i)] > A[i]
        exchange A[i] with A[PARENT(i)]
        i = PARENT(i)

MIN-HEAP-INSERT(A, key)
    A.heapsize = A.heapsize + 1
    A[A.heapsize] = \infty
    HEAP-DECREASE-KEY(A, A.heapsize, key)

Set the key to \(-\infty\) to keep the max heap and ensure that the desired value is larger than the current value.

Initialization: The subarray is same as the original max heap except \(A[i] = key\), and there may exist one exception that \(A[i] = key\) may be larger than \(A[PARENT(i)]\).

Maintenance: We exchange \(A[i]\) with \(A[PARENT(i)]\) if \(A[i] > A[PARENT(i)]\), so the violation becomes that \(A[PARENT(i)]\) may be larger than \(A[PARENT(PARENT(i))]\).

Termination: We terminate when \(i = 1\) or \(A[PARENT(i)] \leq A[i]\), we resolved the violation and the subarray becomes a max heap.

HEAP-INCREASE-KEY(A, i, key)
    if key < A[i]
        error "new key is smaller than current key"
    while i > 1 and A[PARENT(i)] < A[i]
        A[i] = A[PARENT(i)]
        i = PARENT(i)
    A[i] = key

FIFO queue: Use a min-priority queue, increase the priority on every insertion.

Stack: Use a max-priority queue, increase the priority on every insertion and decrease the priority on every extraction.

Note that the priority would keep increasing on total in a FIFO queue, so we need to consider reassignment of the priorities.

HEAP-DELETE(A, i)
    key = A[A.heap-size]
    if A[i] > key
        A[i] = key
        MAX-HEAPIFY(A, i)
    else HEAP-INCREASE-KEY(A, i, key)
    A.heap-size = A.heap-size - 1

MERGE-SORTED-LISTS(L, k)
    let A[1..k] be a new array
    let B be a new array
    for i = 1 to k
        A[i].list-index = i
        A[i].index = 1
        A[i].key = L[i][1]
    BUILD-MIN-HEAP(A)
    while A.heap-size > 0
        B.append(A[1].key)
        if A[1].index < L[A[1].list-index].length
            A[1].index = A[1].index + 1
            A[1].key = L[A[1].list-index][A[1].index]
        else HEAP-EXTRACT-MIN(A)
    return B