# 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);
}