Binary Heap

A Binary Heap is a common way to implement a Priority Queue.

This is because:

1. It has easy access to the root node which can be the min or max depending on implementation
2. Heaps are usually implemented as an array, which guarantees cache friendliness
3. It is easy to insert, search and delete inside of cheaply, in $O(\log n)$ worst case

---

Implementation

A min binary heap is an array as follows:

0	1	2	3	4	5
1	3	6	5	9	8