Open Sourced: A tale of two Priority Queue’s

One of my favorite data structures is the binary heap. I first learned about it in my data structures class, and remember marveling at its simplicity and elegance. How could something so simple be so powerful and useful?

For those unfamiliar with the binary heap, it is a relatively simple data structure. It is a binary tree, which means each node has at most 2 children and n top of this, there are several constraints which are imposed. One is that the the children of each node must have a value that is equal to or greater. This means we have some sort of loose ordering, where nodes closer to the root have a lower value. Secondly, the tree must be complete. This means that all levels of the tree except for the last level must be full, and filled left-to-right. As described, this would be a Min-Heap, since the minimum value is always at the root. If we were to reverse our comparisons, so that the children must be less than or equal to the current node, we would have a Max-Heap with the maximum value at the root.

One of the primary uses of a Min/Max Heap is as a Priority Queue. If one inserts nodes based on their “priority”, then the nodes with the highest priority are at the root.

Below is a example of a Min-Heap, where each node represents a persons age and name. We can see that there is a rough ordering with the youngest person at the root.

Read More