Heap

Heaps are a special kind of tree-based data structure that is an almost complete balanced binary tree (graph with a maximum of two children and all levels are complete except the last one, filled from left to right).

Heaps have two kinds, in a max heap, any node’s value is greater than all children’s value (and children of children); in a min heap, any node’s value is lesser than all children’s value (and children of children).

Heaps are not sorted structures and can be regarded as partially ordered, but there is no order between siblings. They are commonly used for heapsort sorting algorithms, priority queues, and Dijkstra’s algorithm.

The most common implementation is storing elements in an array and using their relative positions to represent child-parent relationships.

As you can see in this array, the tree has been flattened, and we can use the current index to find the following left and right elements. Thanks to being a complete binary, we can find the left and right elements of the current node with a simple formula.