The Heap

The Heap is a data structure similar to binary sort tree structure. New nodes are placed to the heap from the top to bottom and from the left to right. Each parent may have no more than two children.

There are two kinds of heaps:

  • The Max heap, where the root node is the largest element of the entire tree.
  • The Min heap, where the root node is the smallest element of the tree.

When you add elements to the heap you add them to the bottom to the
next available slot to the right or down.

When you remove elements from the heap you remove them from the top. The root should be removed and the last element down the tree takes its place. The the new root is compared with its children and the largest element goes to the place of the root. The same process continues to the bottom of the tree.

To figure out parent and children in array that represents a Heap, use
the following formulas:
Left child index position = 2n + 1 (where the n is the index position of the parent)
Right child index position = 2n + 2 (n is its parent position)

To find a parent of the child use the formula:
Parent index position = ⌊(n-1) / 2⌋ (n is its child position)