m-Ary heaps for sorting and priority queues

mgcadmin 12-07-2023

For most people "heaps" are synonymous with an array based heap ordered binary tree, commonly used as a priority queue. But the forest of heap ordered trees is rich in diversity, with variants including Leftist heaps, Fibonacci heaps, binomial heaps, and randomized meldable heaps just to name a few. Some of these data structures are fairly straight forward, and yet others are rather exotic with tricky implementations.

But there is one type of heap that is often skipped over, despite research showing it to be one of the faster implementations of a priority queue for certain applications. I am talking about the m-Ary heap: the m-way branching cousin of the binary heap.

My original interest in m-Ary heaps stems from a lunch break coding session involving implementing a ternary heap sort. I've since improved both that sorting algorithm, and expanded the implementation to an explicit data structure as well, and since there are precious few examples of this data structure (that I've found at least) I decided to share my implementation with you all. So without further ado....

Let's Get Heapified

No matter what kind of heap you're using, the act of taking a collection of items and arranging them into heap wise order is called "heapifying" and it can be done both top down - starting from parents and then processing their children, and bottom up - starting from children and working up to their parents. This property is actively exploited by priority queues. Like their binary cousins, m-Ary heaps use an implicit array based representation of the underlying tree.

The text book top down implementation of binary heapify is a good place to start, because we can see how it can be easily expanded to ternary heaps and by extension m-Ary heaps.

template <class T>
void heapify(T a[], std::size_t n, int idx) {
     int max = idx;
     int left = 2 * idx;
     int right = 2 * idx + 1;
     if (left < n && a[left] > a[max]) max = left;
     if (right < n && a[right] > a[max] max = right;
     if (max != k) {
        swap(a[max],a[k]);
        heapify(a, n, max);
     }
}

Binary heaps exploit the property of that an array can be used to represent a binary tree, with the children of the value at array slot i begin 2*i and 2*i + 1, respectively. This property does not only hold for binary tree's however, we can implement any branching factor the same way, with the children of i being 2*i through 2*i+n. This allows us to make a simple modification to the above algorithm to change it from binary heapify to m-Ary heapify:

void downheapify(int a[], int n, int k) {
    int max = k;
    for (int child = 2*k; child < (2*k)+M; child++) {
        if (child < n && a[child] > a[max]) max = child;
    }
    if (max != k) {
        exch(a, max, k);
        downheapify(a, n, max);
    }
} 

This algorithm can be used as a drop-in replacement to the heapify algorithm used by heapsort, and being tail recursive, is very easy to reimplement iteratively as shown below, though your compiler is most likely already doing this for you:

const int M = 4;
 
void downheapify(int a[], int n, int k) {
    for (;;) {
        int max = k;
        for (int child = 2*k; child < (2*k)+M; child++) {
            if (child < n && a[child] > a[max]) max = child;
        }
        if (max != k) {
            exch(a, max, k);
            k = max;
        } else {
           break;
        }
    }
}

void make_heap(int a[], int n) {
    for (int i = (n/2) - 1; i >= 0; i--) {
        downheapify(a, n, i);
    }
}

void sort(int a[], int n) {
    make_heap(a, n);
    for (int i = n - 1; i > 0; i--) {
        exch(a,0, i);
        downheapify(a, i, 0);
    }
} 

Now that we have a feel for m-Ary heaps and how they relate to binary heaps, lets take a look at implementing an explicit m-Ary heap data structure.

m-Ary Heap Priority Queues

Heaps make excellent priority queues because they are purpose built for finding either the highest or lowest ordered item in a collection, depending if you are using a min or max ordered heap. The examples shown here are for a Max ordered heap, though you only need to change ONE line of code to switch it to being min ordered. I'll leave that as an exercise for the reader.

All priority queues no matter what kind MUST implement at least the following operations:

• Push an item on to the queue
• Pop the top item off of the queue
• Peek at the top item on the queue
• Tell if the queue is empty

In order to support these operations we will also need to implement:

• downheap(k) - do a downwards heapify of the tree starting from position k
• upheap(k) - do a upwards heapify of the tree starting from position k
• exch(i, j) - swap the elements at positions i and j
• grow() - being array based, we can resize our array in the same way a vector does when to avoid overflowing.

We can use C++ templating for making our heap generic, as well as for defining the "aryness" of the heap:

 
template <class T, int M = 4>
class MultiwayMaxHeap {
    private:
    T* a;
    int n;
    int maxN;
    void exch(int l, int r) {
        T t = a[l];
        a[l] = a[r];
        a[r] = t;
    }
    void grow() {
        T* tmp = new T[2*maxN];
        for (int i = 0; i < n; i++)
            tmp[i] = a[i];
        delete [] a;
        a = tmp;
        maxN *= 2;
    }
    void downheap(int k) {
        for (;;) {
            int max = k;
            for (int child = (2 * k)+1; child <= ((2 * k)+1) + M; child++) {
                if (child < n && a[child] > a[max])
                    max = child;
            }
            if (max != k) {
                exch(max, k);
                k = max;
            } else {
                break;
            }
        }
    } 

We've already covered downheap() above. For the data structure as in the sorting algorithm, I chose the iterative over recursive implementation. upheap() works opposite of downheap(), as the name would suggest, we start from the leaves and work upwards to their parents. In the same way that we can compute an elements children, the operation is reversible to determine an elements parents as well: For any element i its parent cant be found at position (i-1)/M. This fact allows us to work our up the heap, comparing the value of elements and swapping when need be to ensure the tree stays heap ordered.

  
  void upheap(int k) {
        while (k > 1 && a[(k - 1) / M] < a[k]) {
            exch((k - 1) / M, k);
            k = (k - 1) / M;
        }
  } 

And besides for those differences, the rest of the implementation is the same as if it were a binary heaps:

 
public:
    MultiwayMaxHeap() {
        maxN = 255;
        n = 0;
        a = new T[maxN];
    }
    ~MultiwayMaxHeap() {
        delete [] a;
    }
    int size() {
        return n;
    }
    bool empty() {
        return n == 0;
    }
    void push(T k) {
        if (n+1 == maxN) grow();
        a[++n] = k;
        upheap(n);
    }
    T pop() {
        T ret = a[0];
        exch(0, n--);
        downheap(0);
        return ret;
    } 
    T& top() {
        return a[0];
    }
};

So there you have it, full implementations of both m-Ary heap sort and a multiway-heap based priority queue. Use them wisely and happy hacking!

---