# 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.