Binary Heaps

This youtube video is the best explanation I found of heaps.

This page contains about the same content if you need an alternate explanation.

The only thing I would like to add is that it’s possible to build a heap from an unsorted array in $O(n)$ time. Check out wikipedia for more information. Personally, I’ve never had to use this knowledge, and inserting one by one in $O(n\log n)$ is fine.

That’s it for binary heaps!

Priority Queues

Priority queue are an abstract data type that support the following operations:

Since we’re talking about priority queues in this page, you probably already know that you can use binary heaps to implement priority queues. This supports getting the smallest element in $O(\log n)$ time and inserting a new element in $O(\log n)$ time. You can also use a max-heap to get the largest element. Alternatively, you can reverse the sorting order of your objects by changing the < operator.