Problem 6.2

Analysis of d-ary heaps

A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have $d$ children instead of 2 children.

  1. How would you represent a $d$-ary heap in an array?
  2. What is the height of a $d$-ary heap of $n$ elements in terms of $n$ and $d$?
  3. Give an efficient implementation of EXTRACT-MAX in a $d$-ary max-heap. Analyze its running time in terms of $d$ and $n$.
  4. Give an efficient implementation of INSERT in $d$-ary max-heap. Analyze its running time in terms of $d$ and $n$.
  5. Give an efficient implementation of INCREASE-KEY(A, i, k), which flags an error if $k < A[i]$, but otherwise sets $A[i] = k$ and then updates the $d$-ary max-heap structure appropriately. Analyze its running time in terms of $d$ and $n$.

Representation

We just modify LEFT, RIGHT and PARENT. We can get the $k$-th child of the $i$th node with $d i + k - 1$ and the parent with $\lfloor i/d \rfloor$ (when indexing is 1-based).

Height

Of course it's $\log_dn$.

Implementation

The implementation is below. The complexity of EXTRACT-MAX is $\O(d\log_dn)$, while the other two are $\O(\log_dn)$.

C code

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define PARENT(i,d) ((i - 1) / d)
#define CHILD(i,c,d) (3 * i + c + 1)

typedef struct {
    int *elements;
    int d;
    int heap_size;
    int length;
} heap_t;

void max_heapify(heap_t *heap, int i) {
    int largest = i;

    for (int k = 0; k < heap->d; k++) {
        int child = CHILD(i, k, heap->d);
        if (child < heap->heap_size && heap->elements[child] > heap->elements[largest])
            largest = child;
    }

    if (largest != i) {
        int tmp = heap->elements[i];
        heap->elements[i] = heap->elements[largest];
        heap->elements[largest] = tmp;

        max_heapify(heap, largest);
    }
}

int extract_max(heap_t *heap) {
    int max = heap->elements[0];
    heap->elements[0] = heap->elements[heap->heap_size - 1];
    heap->heap_size--;
    max_heapify(heap, 0);
    return max;
};

void increase_key(heap_t *heap, int i, int key) {
    if (key < heap->elements[i]) {
        exit(0);
        fprintf(stderr, "new key is smaller than current key\n");
    }

    while (i > 0 && heap->elements[PARENT(i,heap->d)] < key) {
        heap->elements[i] = heap->elements[PARENT(i,heap->d)];
        i = PARENT(i,heap->d);
    }

    heap->elements[i] = key;
}

void insert(heap_t *heap, int key) {
    heap->heap_size++;
    heap->elements[heap->heap_size - 1] = INT_MIN;
    increase_key(heap, heap->heap_size - 1, key);
}