Recently I had an opportunity of solving one of more famous algorithmic problems using JavaScript. One of the approaches to this problem is to use Priority Queue data structure to keep track of most frequent items. Unfortunately, JavaScript doesn't have standard implementation for such data structure.

So - let's build one.

The idea behind a priority queue (and binary heap as well) is simple - maintain elements in an array, while mimicking a behavior of complete binary tree. In other words - every tree level, except possibly the last one, is completely filled, and all nodes on the last level are located as far left as possible.

Now, what this structure gives us in terms of time complexity when we want to add to a queue, or remove from it?

Let's take a look at add operation first.
When we add new item to a queue, it is appended to an end of an array. Because we want highest priority element to be the first in our array, we need to push our new element to a highest possible level of our complete binary tree. How it's done? We know the array index of newly added element, let's call it 'i'. The index of a parent element equals (i-1)/2 (it's a complete binary tree after all). Now, we need to compare parent's and child's priorities, and swap those if child's priority is higher than parent's. This process of comparing and swapping continues until new element either becomes a root of our tree (i = 0) or it hits a parent with higher priority. Overall, this "sifting up" process takes O(log N) time because 'i' index is split in half on each iteration.

Queue's remove operation is actually slightly more complicated.
The nature of adding new item into the queue guarantees that first element of underlying array is the element that has the highest priority. This first element is the result that's returned.
Now, when result is extracted from the queue, how to update our tree to maintain highest priority item on top? For this we can move last array element to '0' index (i = 0) and perform steps opposite to those of adding - compare root with left (i*2 + 1) and right (i*2 + 2) subtrees and swap root with one of them if root's priority is less than subtree's priority. Repeat until we either run out of subtrees (end of the array) or root has higher priority than its children. This "sifting down" takes O(log N) time as well.

So, how exactly all of this maps to an actual JavaScript code?
For that I've put a simple class that implements priority queue while expecting from queued objects to expose .priority property (duck-typing for the win!):