Understanding priority queues/heaps

Priority queues are queues where each element has a priority. An element with high priority is served before an element with low priority.

For example, consider we have a task queue where tasks are inserted and need to be executed. A high priority task may appear after some tasks are inserted in the queue; however, it would need to be executed prior to tasks with low priority.

There are min-heaps and max-heaps. Min-heaps always have the least element as their root, which would be readily accessible. For max-heaps, the max element will be the root.

Let's look at the min-heap data structure first and then the functional version. Heaps are complete binary trees.

For more on the definition, visit http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html .

The nodes also have partial ordering such that the root value is always less that its children. You will get this if you've been a keen observer all this while: this is an invariant.

In the imperative...