6-2 Analysis of $d$-ary heaps

A $d$-ary heap is like a binary heap, but (with one possible exception) nonleaf nodes have $d$ children instead of two children. In all parts of this problem, assume that the time to maintain the mapping between objects and heap elements is $O(1)$ per operation.

a. Describe how to represent a $d$-ary heap in an array.

b. Using $\Theta$-notation, express the height of a $d$-ary heap of $n$ elements in terms of $n$ and $d$.

c. Give an efficient implementation of EXTRACT-MAX in a $d$-ary max-heap. Analyze its running time in terms of $d$ and $n$.

d. Give an efficient implementation of INCREASE-KEY in a $d$-ary max-heap. Analyze its running time in terms of $d$ and $n$.

e. Give an efficient implementation of INSERT in a $d$-ary max-heap. Analyze its running time in terms of $d$ and $n$.

a

The array can be described by the following two fuctions to get the index of parent of $i$-th element in the array and the $j$-th child of $i$-th element.

$$\begin{aligned} CHILD(i+1,j) & = CHILD(i)+d\cr CHILD(1,j) & = j+1 \quad 1\leq j \leq n\cr \implies CHILD(i,j) & = d(i-1)+j+1 \quad 1\leq j \leq n\cr \implies PARENT(i) & = floor((i-2)/d) + 1\cr \end{aligned}$$

b

Let $max(h)$ be the maximum numbers of elements in a $d$-ary heap of height $h$? Let $h(n)$ be the height of $d$-ary heap of $n$ elements.

$$\begin{aligned} max(h) & = \sum_{i=0}^{h} d^i\cr & = \frac{d^{h+1}-1}{d-1}\cr h(n) & = \Theta(\log_{d}h)\cr & = \Theta(\lg n)\cr \end{aligned}$$

c

D-ARY-MAX-HEAP-EXTRACT-MAX(A)
    max = A[1]
    A[1] = A[n]
    A.heap-size = A.heap-size - 1
    D-ARY-MAX-HEAP-HEAPIFY(A,1)//Θ(d*lg(n))
    return max

//
D-ARY-MAX-HEAP-HEAPIFY(A,i)
    find the index j of the largest child of A[i]//Θ(d)
    if j != i
    exchange A[i] and A[j]
    i = j
    D-ARY-MAX-HEAP-HEAPIFY(A,i)//Θ(lg n) times' calling

The running time of EXTRACT-MAX $\Theta(d\lg n)$.

d

D-ARY-MAX-HEAP-INCREASE-KEY(A,x,k)
    if k < x.key
        error "new key is smaller than current key"
    find the index i in array A where object x occurs
    while i > 1 and A[i].key < A[PARENT(i)].key
        exchange A[i] and A[PARENT(i)]
        update relative information
        i = PARENT(i)

The number of while loop iteration is the depth of the node which denotes x. So the running time is $O(D)=O(\log_{d} n)$

e

D-ARY-MAX-HEAP-INSERT(A,x,n)
    if A.heap-size == n
        error "heap overflow"
    A.heap-size = A.heap-size + 1
    k = x.key
    A[A.heap-size] = x
    x.key = -∞
    update the map between objects and array
    D-ARY-MAX-HEAP-INCREASE-KEY(A,x,k)

The running time is domained by D-ARY-MAX-HEAP-INCREASE-KEY(A,x,k). So it is $O(\log_{d} n)$