3. The Heap Data Structure

Now that we understand the concept of a binary tree, we can define a Heap. A Heap is a specialized tree-based data structure that satisfies two specific properties.

The Two Defining Properties of a Heap

For a binary tree to be considered a Heap, it must adhere to the following rules:

1. Structure Property: It must be an Essentially Complete Binary Tree.
   This means that the tree is completely filled on all levels, with the possible exception of the last level, which must be filled from left to right without any gaps. This "no gaps" property is crucial, as it allows a heap to be stored efficiently in an array.

2. Heap Property (Order Property): The nodes must be ordered in a specific way relative to their children. This ordering defines the type of heap.

Types of Heaps

There are two main types of heaps, distinguished by the Heap Property they enforce:

• Max-Heap: The value of every node is greater than or equal to the value of each of its children.

  • Implication: In a Max-Heap, the largest element in the entire collection is always located at the root of the tree. This is the type of heap used for Heap Sort.

  • Example: A tree with root 10 and children 8 and 9 is a valid Max-Heap at the top level.

• Min-Heap: The value of every node is less than or equal to the value of each of its children.

  • Implication: In a Min-Heap, the smallest element is always located at the root. This structure is commonly used to implement Priority Queues.

  • Example: A tree with root 2 and children 5 and 3 is a valid Min-Heap at the top level.

The Array Representation

The complete binary tree property is precisely what makes an array a perfect and highly efficient way to store a heap. The hierarchical relationships are not stored with pointers, but are instead calculated mathematically based on an element's index.

For an element at a zero-based index i in an array representing a heap:

• The index of its parent is calculated as: floor((i - 1) / 2)

• The index of its left child is calculated as: 2 * i + 1

• The index of its right child is calculated as: 2 * i + 2

For example, for the node at index i = 3:

• Its parent is at index floor((3 - 1) / 2) = floor(1) = 1.

• Its left child would be at index 2 * 3 + 1 = 7.