n–ary heap

An a–ary heap, also called d–ary heap and n–ary heap, is an array-based data structure that is a representation of a complete (i.e. almost full (full i.e. each node has either zero or a children, and those with zero children are at same depth), that is as if from a full tree were possibly some depthmost nodes removed from rightmost but leaving at least one) a-ary tree — with children of each parent p being at ap−b+k for k-th children numbered from 1, where b is the first (leftmost) index of the array — that satisfies the heap property which states that children are, in case of max-heap, less or equal (in case of min-heap, greater or equal) to the parent.

It is a generalisation of binary heap.

For any given index x of a child node, the index p of its parent can be calculated with the formula ⌊(x+b−1)∕a⌋ where b is, again, the first (leftmost) index of the heap's underlying array. To avoid machine integer overflow, equivalent formula ⌊x∕a⌋+⌊((x mod a)+b−1)∕a⌋ can be used. This formula is useful to calculate what would be the last parent node in a heap of a given length.

(b is 0 in standard C/Java/Go arrays and Python lists if whole array is used for the heap, and typically 1 in algorithm descriptions and also many programming languages)

In the pseudocode below, A'First is the first index of an array A, earlier mentioned in formulas as b.

procedure siftDown(A, e, f)
if e≠f then
t := f
furthest_parent := furthestParent(e)
while t≤furthest_parent loop
j := t
for i := leftChild(t) to max(leftChild(t)+a−1, e) loop
if A[j] < A[i] then
j := i
if j=t then
exit loop
swap(A[t], A[j])
t := j

To reiterate, what siftDown does is, starting with a given node, comparing the selected node to its children, and if the largest child is larger than the selected node, swapping them and repeating the procedure for the index of the node that we just moved down, otherwise being done.

It could be thought as taking the a+1 nodes and rotating them (and then doing the same with the one previously on top), like what we know from balancing a–ary search trees, except here the order of the children doesn't matter and thus we make just one swap instead of a — but that can be considered as but an optimization.

Under the assumption that all (less than or a) subheaps — children of our given node — satisfied the heap property on their own, the (sub- — if f>b)heap resulting from siftDown satisfies the heap property entirely.

procedure heapify(A, e)
if e≠A'First then
furthest_parent := furthestParent(e)
for i := furthest_parent downto A'First loop
siftDown(A, e, i)

Since single-element (sub)heaps satisfy the heap property always, what heapify does is, by starting with the furthest node that is a parent to any children (between 1 and a) and performing siftDown on it, thus always satisfying the precondition of siftDown by having the subheaps already performed upon. Thus from that, after it reaches the root of heap and performs siftDown on it, the whole heap satisfies the heap property.

procedure heapsort(A, e)
if e≠A'First then
heapify(A, e)
h := e - 1
while h > A'First then
swap(A, h, A'First)
h := h − 1
siftDown(A, h, A'First)

And heapsort first takes an array that is unassumed to be either sorted or a heap, then makes it satisfy the heap property entirely by performing heapify on it, then takes the largest element — from the heap property, the first one — and shortens the heap by putting it behind and placing the previously leaf-of-heap element on top, then performing siftDown on the lenght of the new heap which is one less than before — and then again, takes the largest element… so on. Finally it ends up with just one element, which is in same place as is it supposed to be by the order, the array being entirely sorted.

Much of this article is just an alteration of the article on binary heap and heapsort, hence an implementation of heapsort and everything.

See also:

Trivia