Heap

• The binary heap is an array that we can view as a nearly complete binary tree.
• The tree is filled except possibly the lowest part, which is filled from the left up to a point.

An array A representing an heap is characterized by two attributes:

• length: number of elements/slots
• heap_size: number of elements stored/valid

The following are other common characteristics:

• Height: longest simples downward path
  • If the heap is a binary tree -> height ~ O(log n)
• Heap operations run O(log n)

If the root of the tree is A[1], given the index i we can easily compute parents and children:

• parent(i): floor i/2 (binary shift right)
• left(i): 2i (binary shift left)
• right(i): 2i + 1

Note, if root is A[0] =>

def parent_left_right_indices(i):
    parent = (i - 1) // 2 if i != 0 else None
    left_child = 2 * i + 1
    right_child = 2 * i + 2
    return parent, left_child, right_child

Two types of heaps:

• Max-heap (max at root)

  • Heap-property => A[Parent(i)] $\geq$ a[i]

• Min-heap (Min at root, commonly used to implement priority queues)

  • Heap-property => A[Parent(i)] $\leq$ a[i]

• Max Heap

• Heap Sort

• JAVA: Max-Heap

• JAVA: Min-heap