Swiz Heaps: A deterministic modification of Randomized Meldable Heaps

mgcadmin 09-04-2025

Heaps are a family of trees frequently employed  as priority queues as they allow the efficient location of the minimum (or maximum) element in a collection. They do this by enforcing the heap property which states that no child node has a value lower than that of it's parent. The most common type of heap used for this purpose is the standard binary heap which uses an array representation of a complete binary tree which adheres to the heap property.

More often than not the binary heap will suit your needs which is why so may languages choose it for their standard libraries. If however, you require that your priority queue supports the efficient changeing of an elements priority, or the mergeing of two priority queues then we're going to need something more... flexible.

Pointer Based Heaps

To enable the facilitation of changing prioirty and merging priority queues we need to change the underlying representation used for the heap. The array based complete binary tree of the binary heap is too rigid, so instead we use a pointer based tree. This holds true for Fibonacci heaps, Bionmial Queues, Leftist heaps, Skew heaps, and Randomized Heaps.

struct node {
       T info;
       shared_ptr<node> left;
       shared_ptr<node> right;
       node(T i, shared_ptr<node> ll, shared_ptr<node> rr) : info(i), left(ll), right(rr) { }
};
using link = shared_ptr<node>;

A standard binary tree node will serve our purposes just fine.

Randomized Meldable Heaps

If you are familiar with either Skew heaps or Leftist heaps, than the following algorithm will look pretty familiar. Both of the aformentioned types of heaps, in addition to Randomized Meldable heaps (and now Swiz Heaps) all rely on a merge (or meld) function to construct the heaps. 

Leftist heaps and skew heaps trade balance for simplicity. Randomized meldable heaps gain balance (with high probability) through randomness. Of the three, randomized heaps are the easiest to understand and implement. 

link merge(link lhs, link rhs) {
        if (lhs == nullptr) return rhs;
        if (rhs == nullptr) return lhs;
        if (cmp()(lhs->info, rhs->info)) return merge(rhs, lhs);
        if (rand() % 2 == 0) {
            lhs->left = merge(lhs->left, rhs);
        } else {
            lhs->right = merge(lhs->right, rhs);
        }
       return lhs;
} 

Unfortunately, there are many scenarios where be it for selecting a quicksort pivot, or whether or not to promote a level in a skip list, or how to merge two heaps - where depending upon randomization is not acceptable for one reason or another. The question then is, in those situations how can we preserve the favorable balance of randomized heaps and their ease of implementation, while avoiding stepping into the void of randomization?

Swiz Heaps

Swiz heaps work on a very simple principle: If on the last call to merge() we favoried the left child, then on the current call to merge() we favor the right child. This has the effect of us "zig-zagging" across the child nodes based on a "switch", or "swizzing" a value into place.

link merge(link lhs, link rhs) {
            if (lhs == nullptr) return rhs;
            if (rhs == nullptr) return lhs;
            swiz = !swiz;
            if (cmp()(lhs->info, rhs->info)) return merge(rhs, lhs);
            if (swiz) {
                lhs->left = merge(lhs->left, rhs);
            } else {
                lhs->right = merge(lhs->right, rhs);
            }
            return lhs;
} 

This one slight modification allows us to remove the dependence on randomeness while still preserving the "generally good enough" balance of a randomized meldable heap! The other operations stay completely unchanged from the randomized implementation.

void push(T info) {
      root = merge(root, new node(info));
      count++;
}

T pop() {
     T ret = root->info;
     root = merge(root->left, root->right);
     count--;
}

Well, thats what I've got for today. Until next time, Happy Hacking!

---