Priority queue – part three

You might have thought that the last couple of posts would have done it for the priority queue – after all, we have the optimal heap implementation for it – but no. There are a couple more fun bits. Let’s investigate a little bit more.

The push and pop operations are both O(log(n)). The reason for this is that the height (or depth, if you prefer) of a complete tree is log(n). So when we bubble up or trickle down we’ll move the item at most log(n) levels. Notice that bubble up uses at most log(n) comparisons to find the right place for the item, whereas trickle down uses at most 2*log(n) comparisons (we have to compare both children together as well as compare the parent against the larger child). So, all in all, trickle down will be about twice as slow as bubble up, if we ignore the time take to move items up or down (we just note that comparisons are in general more expensive in time), so it’s worth pointing out an optimization here with regard to trickle down.

Trickling down faster…

There is a small but effective change we can make to speed up the trickle down operation. If you look back to my description of trickle down, I mentioned that the item we promote to the root is going to be one of the smallest items in the tree. In other words, it’s extremely likely that the item will find itself down on the lowest level again once the trickle down is complete. In yet more other words, it’s fairly pointless performing the larger child to parent comparison as we trickle down: we should always assume that the item is going to make it down to the lowest level and therefore we should always swap the parent item with the larger of its children’s items.

But that raises a problem: we may go too far. It’s not 100% guaranteed that the item will find its correct position all the way down on the lowest level; it’s just pretty likely. However, we may end up with the item on the lowest level, but with it being larger than its parent. No problem: just perform a bubble up on it to restore the heap property. In general we won’t have to bubble up very far.

In fact, because we’re assuming the most likely scenario that the item will work its way all the way to the bottom level, we’ll speed up trickle down as a whole. For the not so likely scenario (the item shouldn’t actually end up on the lowest level), we’ll be slightly slower. But get this: on average, trickle down will be faster with this optimization.

  var trickleDown = function (index, item) {
    // calculate the index of the left child
    var child = (index * 2) + 1;

    // if there is one...
    if (child < queue.length) {

      // work out the larger of the left and right children
      if (child + 1 < queue.length) {
        if (comparer(queue[child], queue[child + 1]) < 0) {
          child += 1;
        }
      }

      // move the larger child up, trickledown from that child's position 
      queue[index] = queue[child];
      trickleDown(child, item);
    }
    else {
      // reached the lowest level, so bubbleup from our current position
      queue[index] = item;
      bubbleUp(index, item);
    }
  };

So that’s it for the priority queue. Because of the definition of the heap property, the priority queue will present its items in reverse order of priority, the largest first. The heap is usually known as a max-heap because it’s built to return the maximum item every time. We could, of course, change the heap property so that parents are smaller than their children, and we’d get a min-heap out of it, or a priority queue that returns items in ascending order of priority.

The min-max Heap

How about a priority queue that could return either the maximum or the minimum, at your whim? Choosing a max-heap wouldn’t work since we’d have a problem finding the minimum (actually it’s a O(n) problem since the smallest item would be at a leaf of the tree, so we’d just need to visit all the leaves). Choosing a min-heap would have the reverse problem, simple and quick to get the minimum, less efficient to get the maximum.

Enter the min-max heap. This heap is so organized that it’s both simple and quick to find either the maximum or the minimum. Both will be O(log(n)) operations, in fact.

function createPriorityDeque(comparer) {
  "use strict";
  var queue = [];

  // lots of code!

  return {
    push: push, 
    popMax: popMax,
    popMin: popMin
  };
}

How is it done? Well, we organize the heap to have yet another heap property. This time the description is a little more complex. Imagine a layer cake, with alternate layers of chocolate and vanilla sponge. The top layer (the root) is less than both its children. The nodes in the next layer (the children of the root) are greater than their children. The next layer the order is reversed again, the parents being less than their children. And so on; each layer swapping the ordering from the previous one. If you like, the nodes in the even layers (0, 2, 4, etc, with the root being at layer 0) are less than their children (in the code, we’ll call this a min layer), whereas the nodes in the odd layers (1, 3, 5, etc) are greater than theirs (a max layer). We shall further arrange things so that a node in an even layer is smaller than its grandchildren, and that a node in an odd layer is greater than its grandchildren. It’s like a max-heap interleaved with a min-heap.

Another way of seeing this is to say that if a node appears on a min layer it will be less than all of its descendants (children, grandchildren, great-grandchildren, etc). If a node is in a max layer, it will be greater than all of its descendants.

What does this complexity get us? To begin with the smallest item will be found at the root, and the largest item will be found in one of the root’s children. All well and good but we’d better make sure that we can build such a heap, and that we can retrieve the maximum and minimum items when needed, otherwise it’s all castles in the air.

More bubbling up…

Insertion first. We’ll do the same thing as we did for the simpler heap: add it to the last layer, at the leftmost node position. This will enforce the complete binary tree attribute. Now, though, we have a choice of what to do.

If the item was added to an even level, it is in a min layer and so it has to be less than its parent. So we first compare the item against its parent.

If it is greater than its parent, we swap it over. From this point onwards we are going to be bubbling up the odd layers. Now compare the item against its grandparent (if it has one), if it is larger swap them over, and continue. Once we get to a point where the item has no grandparent, or is not greater than it, we stop. So the effect is that we bubble up one layer, and then every other layer.

If, at the start, it was less than its parent, the item is in the correct place as far as the max layers are concerned. It may, however, be out of place, in the min layers. So we compare it against its grandparent. If it is less than the grandparent, swap it, and do the same thing at the new level. Eventually, you will either reach the root or you’ll find that the grandparent is smaller. So we would bubble up every other layer in this case.

Of course, if the item was added to an odd level, it’s in a max layer and so has to be greater than its parent. If it isn’t, swap them over, and then bubble up through the min layers, skipping the max layers. If it is greater than the parent, we bubble up through the max layers, skipping over the min layers.

  // *** FUNCTIONS USED FOR BOTH PUSH AND POP
  var getParent = function (index) {
    // for index 0, there is no parent
    if (index === 0) {
      return -1;
    }
    return (index - 1) >> 1;
  };

  var getGrandparent = function (index) {
    // for indexes 0, 1, 2, there is no grandparent
    if (index <= 2) {
      return -1;
    }
    return (index - 3) >> 2;
  };

  var isLarger = function (a, b) {
    return comparer(a, b) > 0;
  };

  var isSmaller = function (a, b) {
    return comparer(a, b) < 0;
  };

  // *** FUNCTIONS USED FOR PUSH
  var isOnMinLevel = function (index) {
    // top level is a min level, index is 0
    // next level is a max level, indexes are 1, 2
    // third level is a min level, indexes are 3, 4, 5, 6
    // fourth level is a max level, indexes are 7 - 14
    // etc

    // so to determine which type of level an index is, we
    // add 1 to it, and then count the number of times we can
    // divide by 2 until we get to 0. 
    // If the count is odd, it's a min level

    var i = 0;
    index += 1;
    while (index !== 0) {
      index = index >> 1;
      i += 1;
    }
    return (i % 2) === 1;
  };

  var bubbleUpOrdered = function (index, item, isOrdered) {
    // bubble up through grandparent levels until we no longer have one
    var grandparent = getGrandparent(index);
    while ((grandparent >= 0) && isOrdered(item, queue[grandparent])) {
      queue[index] = queue[grandparent];
      index = grandparent;
      grandparent = getGrandparent(index);
    }
    queue[index]= item;
  };

  var bubbleUp = function (index, item, isOrdered, isReverseOrdered) {
    // first check that this item is correctly ordered with the parent
    var parent = getParent(index);
    if (isReverseOrdered(item, queue[parent])) {
      // if not, bring the parent item down, 
      // then bubble up from the parent's position
      // but remember that we've switched min/max layer type
      queue[index] = queue[parent];
      bubbleUpOrdered(parent, item, isReverseOrdered);
    }
    else {
      // otherwise just bubble up from where we are
      bubbleUpOrdered(index, item, isOrdered);
    }
  };

  var push = function (item) {
    // add the item to the end
    queue.push(item);

    // only bubble up if needed
    if (queue.length > 1) {
      var index = queue.length - 1;
      if (isOnMinLevel(index)) {
        bubbleUp(index, item, isSmaller, isLarger);
      }
      else { 
        bubbleUp(index, item, isLarger, isSmaller);
      }      
    }
  };

I’m sure you’re beginning to see the picture: we’re treating the min-max heap as two interleaved ordinary heaps and use much the same bubble up method we used before (except we jump over intervening layers).

And trickling down…

Trickle down is a little more complex, so let’s take it slowly.

Suppose we had to remove the smallest item. This is at the root, so we remove it, and swap in the item that’s at the leftmost position on the bottommost level. The item is now on a min layer.

  var popMin = function () {
    // take care of easy cases
    if (queue.length === 0) {
      return null;
    }
    if (queue.length === 1) {
      return queue.pop();
    }

    // the min item is at the root
    // trickle down from there
    var min = queue[0];
    queue[0] = queue.pop();
    trickleDownOrdered(0, isSmaller);
    return min;
  };

Assume first that the node has all four grandchildren. Find the smallest grandchild. If the item we’re positioned at is greater than this smallest grandchild, swap them over. If, in its new position, the item is greater than its parent, swap them over. Now repeat this process from the grandchild’s position (whether you did the swap with the parent or not). Essentially we’re trickling the item down the min layers.

Eventually, you’ll reach a point where all four grandchildren are not present. You are in fact either at the lowest level or just above it. Find the smallest of both the children and grandchildren (if they exist). If the smallest is smaller than the item at which we’re positioned, swap them over. If we just swapped with a grandchild, just check to see whether we need to swap with the grandchild’s parent as well, and do so if needed.

  // *** FUNCTIONS USED FOR POP
  var getLeftChild = function (index) {
    return (index * 2) + 1;
  };

  var getLeftGrandchild = function (index) {
    return (index * 4) + 3;
  };

  var itemExists = function (index) {
    return index < queue.length;
  }

  var hasChild = function (index) {
    return itemExists(getLeftChild(index));
  };

  var hasEveryGrandchild = function (index) {
    return itemExists((index * 4) + 6);
  };

  var isGrandchild = function (index, descendant) {
    var grandchild = getLeftGrandchild(index);
    return (grandchild <= descendant) && (descendant <= grandchild + 3);
  };

  var getExtremumGrandchild = function(index, isOrdered) {
    // get the index of the largest/smallest grandchild
    // only called if all 4 grandchildren are present
    var extremum = getLeftGrandchild(index);
    var grandchild = extremum;
    for (var i = grandchild + 1; i <= grandchild + 3; i += 1) {
      if (isOrdered(queue[i], queue[extremum])) {
        extremum = i;
      }
    } 
    return extremum;
  };

  var getExtremumDescendent = function (index, isOrdered) {
    // find the index of the largest/smallest child/grandchild
    // only called if there is at least one child

    // check children first
    var extremum = getLeftChild(index);
    var next = extremum + 1;
    if (itemExists(next) && isOrdered(queue[next], queue[extremum])) {
      extremum = next;
    }

    // now check grandchildren, if they exist
    next = getLeftGrandchild(index);
    if (itemExists(next)) {
      var rightmostGrandchild = next + 3;
      if (!itemExists(rightmostGrandchild)) {
        rightmostGrandchild = queue.length - 1;
      }
      while (next <= rightmostGrandchild) {
        if (isOrdered(queue[next], queue[extremum])) {
          extremum = next;
        }
        next += 1;
      }
    }

    return extremum;
  };

  var swapItems = function(a, b) {
    var x = queue[a];
    queue[a] = queue[b];
    queue[b] = x;
  };

  var checkAndSwapWithParent = function (index, isOrdered) {
    var parent = getParent(index);
    if (!isOrdered(queue[index], queue[parent])) {
      swapItems(index, parent);
    }
  };

  var trickleDownOrdered = function (index, isOrdered) {
    var extremum;
    while (hasEveryGrandchild(index)) {
      extremum = getExtremumGrandchild(index, isOrdered);
      if (isOrdered(queue[index], queue[extremum])) {
        return;
      }
      swapItems(index, extremum);
      checkAndSwapWithParent(extremum, isOrdered);
      index = extremum;
    }
  
    if (hasChild(index)) {
      extremum = getExtremumDescendent(index, isOrdered);
      if (isOrdered(queue[index], queue[extremum])) {
        return;
      }
      swapItems(index, extremum);
      if (isGrandchild(index, extremum)) {
        checkAndSwapWithParent(extremum, isOrdered);
      }
    }
  };

That’s it for the “removal of the minimum item” case.

For the other case (removal of the maximum item), we first work out which of the root’s children contains the larger item and remove that, replacing it with the last item in the heap. This item now finds itself in a max layer.

And guess what? You trickle down the max layers in exactly the same manner as we did for the min layers just now. The same process, except we’re looking for the largest of the item’s grandchildren, etc.

  var popMax = function () {
    // take care of easy cases
    if (queue.length === 0) {
      return null;
    }
    if (queue.length < 3) {
      return queue.pop();
    }

    // the max item is either at index 1 or 2
    // find it, trickle down from there
    var index = 2;
    if (isLarger(queue[1], queue[2])) {
      index = 1;
    }
    var max = queue[index];
    queue[index] = queue.pop();
    trickleDownOrdered(index, isLarger);
    return max;
  };

This listing completes a double-ended priority queue that wraps this min-max heap algorithm. Since a double-ended queue is known as a deque, pronounced DECK, this is sometimes known as a priority deque.

Summary

And with that we come to the end of a fascinating look into a heap structure that gives you the ability to add a bunch of items to it and either remove the largest or the smallest. The structure works faster than a binary search tree with a balancing algorithm (like AVL trees or red-black trees) and faster than a skip list, mainly because maintaining the heap property is simpler than maintaining a full sort order. If you have a need of a black box class for retrieving a set of items in order, either ascending or descending, without having to iterate through the items in the container, the min-max heap is your friend.

(A long time ago I used to write a monthly algorithms column for The Delphi Magazine, called Algorithms Alfresco. This was a Delphi programmer magazine in the UK, which sadly closed down in 2007. I've decided to reuse/revamp those articles in a long series here on my blog, but coding in JavaScript instead of Delphi. This article first appeared in the July 2004 issue.)

  Loading links to posts on similar topics...