Heaps

Heaps are trees, but with a specific requirement.

• Root node will have the smallest/largest value. This is the main rule which makes heaps useful. Every peek() always returns the next smallest/largest value.
• Every node will have a value lesser (or greater for max-heap) than its children.
• The tree isn't sorted like in the binary search tree.

Heap vs Priority Queue

A Priority Queue isn't a data structure. It's only a class with specific requirement which says, the class returns always the next person in the queue based on the priority.

Priority Queue implements this feature using heaps.

How heaps are stored?

Heaps just use an array to store its nodes. This is exactly why it needs a complete tree since it can't have empty spots in the array.

Updating the root

The most interesting part of heaps is updating the root. Since it's only use case is to ensure retrieving the max or min value in $O(1)$, once the current value is used up, the next root value must be bubbled up to the root. This happens in $O(log N)$ runtime.