Chapter 6 problems

a.

No, consider \(A = \langle 1, 2, 3 \rangle\), BUILD-MAX-HEAP(A) returns \(\langle 3, 2, 1 \rangle\), and BUILD-MAX-HEAP'(A) returns \(\langle 3, 1, 2 \rangle\).

b.

The worst case appears when the input A is already sorted, the running time of BUILD-MAX-HEAP' is

a.

We could define PARENT and CHILD as below to represent a d-ary heap.

PARENT(i, d)
    return (i + d - 2) // d

CHILD(i, j, d)
    // the jth child of node i
    return (i - 1) * d + 1 + j

b.

The height of a d-ary heap of n elements is \(\lfloor\log_{d}((n - 1)(d - 1) + 1)\rfloor\).

c.

The running time is \(\Theta(d\log_d n)\).

EXTRACT-MAX(A)
    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)
    return max

MAX-HEAPIFY(A, i)
    largest = i
    for j = 1 to A.d
        child = CHILD(i, j, d)
        if child > A.heap-size
            break
        if A[child] > A[largest]
            largest = child
    if largest != i
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A, largest)

d.

The running time is \(O(\log_d n)\).

INSERT(A, key)
    A.heap-size = A.heap-size + 1
    A[A.heap-size] = -\infty
    INCREASE-KEY(A, A.heap-size, key)

e.

The running time is \(O(\log_d n)\).

INCREASE-KEY(A, i, key)
    if key < A[i]
        error "new key is smaller 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)

a.

The Young tableau is as below

b.

\(Y[1, 1]\) is the smallest element of \(Y\), and \(Y[1, 1] = \infty\), so Y is empty.

\(Y[m, n]\) is the largest element of \(Y\), and \(Y[m, n] < \infty\), so Y is full.

c.

EXTRACT-MIN(Y)
    min = Y[1, 1]
    Y[1, 1] = \infty
    YOUNG-TABLEAUFY(Y, 1, 1)
    return min

YOUNG-TABLEAUFY(Y, r, c)
    right = (r, c + 1)
    below = (r + 1, c)
    if right <= (Y.m, Y.n) and Y[right] < Y[r, c]
        smallest = right
    else smallest = (r, c)
    if below <= (Y.m, Y.n) and Y[below] < Y[smallest]
        smallest = below
    if smallest != (r, c)
        exchange Y[r, c] with Y[smallest]
        YOUNG-TABLEAUFY(Y, smallest)

The running time is \(T(p) = T(p - 1) + O(1) = O(m + n)\).

d.

YOUNG-TABLEAU-INSERT(Y, key)
    if Y[Y.m, Y.n] < \infty
        error "the Young tableau is already full"
    Y[Y.m, Y.n] = key
    i = Y.m
    j = Y.n
    while i >= 1 and j >= 1
        left = (i, j - 1)
        above = (i - 1, j)
        if left >= (1, 1) and Y[left] > Y[i, j]
            largest = left
        else largest = (i, j)
        if above >= (1, 1) and Y[above] < Y[largest]
            largest = above
        if largest != (i, j)
            exchange Y[i, j] with Y[largest]
            (i, j) = largest
        else return

e.

YOUNG-TABLEAU-SORT(A, n)
    let Y[n, n] to be new Young tableau
    for i = 1 to n * n
        YOUNG-TABLEAU-INSERT(Y, A[i])
    for j = 1 to n * n
        A[j] = EXTRACT-MIN(Y)

First we create a new Young tableau Y[n, n], it costs \(O(n^2)\) running time.

Then we insert the \(n^2\) elements into Y, it costs \(O(n^3)\) running time.

At last, we extract the \(n^2\) elements from Y, it costs \(O(n^3)\) running time, the total running time is \(O(n^3)\).

f.

YOUNG-TABLEAU-SEARCH(Y, key)
    i = Y.m
    j = 1
    while i >= 1 and j <= Y.n
        if key == Y[i, j]
            return (i, j)
        if key < Y[i, j]
            i = i - 1
        else j = j + 1
    return False