Heap Properties and Examples

Heap Properties and Examples

A heap is a specialized binary tree-based data structure that satisfies the heap property. The heap property is defined as follows:

1. Max-Heap Property: In a max-heap, the value of each node is greater than or equal to the values of its children, and the largest element is always at the root of the tree.

2. Min-Heap Property: In a min-heap, the value of each node is smaller than or equal to the values of its children, and the smallest element is always at the root of the tree.

Heaps are generally used to implement priority queues, and they support efficient operations like inserting elements, extracting the maximum or minimum, and building the heap from an unsorted array.

Heap Properties

1. Shape Property:

   • A heap is a complete binary tree, meaning that all levels of the tree are completely filled except possibly the last level, which should be filled from left to right. This property ensures that the tree is balanced and optimally structured for heap operations.

2. Heap Property:

   • Max-Heap Property: For any given node, the value of the node is greater than or equal to the values of its children.
   • Min-Heap Property: For any given node, the value of the node is smaller than or equal to the values of its children.

Heap Operations

Heaps support the following key operations:

• Insertion: Add a new element to the heap and restore the heap property.
• Extracting the Root: Remove and return the root (maximum in a max-heap or minimum in a min-heap), and restore the heap property.
• Peek: Retrieve the root element without removing it from the heap.
• Heapify: Maintain the heap property for a given subtree.
• Building the Heap: Convert an unsorted array into a heap.

Max-Heap Example

Let’s go through an example of a Max-Heap.

Given an array of elements:

[10, 20, 5, 6, 1, 8]

We will convert this array into a max-heap step-by-step.

Step 1: Build the Max-Heap

We will apply the heapify operation starting from the last non-leaf node (index n/2 - 1).

1. Initial array:

   [10, 20, 5, 6, 1, 8]
   

   • Index 2 (Node 5): The left child is 8, and the right child is out of bounds (no child). Since 8 is larger than 5, we swap them:

   [10, 20, 8, 6, 1, 5]
   

2. Index 1 (Node 20): The left child is 6, and the right child is 1. Since 20 is already larger than both, no swap is needed.

3. Index 0 (Node 10): The left child is 20, and the right child is 8. Since 20 is the largest, we swap 10 and 20:

   [20, 10, 8, 6, 1, 5]
   

   Now, heapify is applied to the subtree rooted at index 1.

   • Index 1 (Node 10): The left child is 6, and the right child is 1. Since 10 is larger than both, no swap is needed.

Max-Heap Structure

After these steps, the array represents the following max-heap structure:

        20
       /  \
     10    8
    /  \  /
   6   1 5

Max-Heap Properties

1. The shape property is satisfied because the tree is a complete binary tree.
2. The heap property is satisfied because each parent is greater than or equal to its children.

Min-Heap Example

Let’s now consider an example of a Min-Heap.

Given the same array of elements:

[10, 20, 5, 6, 1, 8]

We will convert this array into a min-heap.

Step 1: Build the Min-Heap

We will apply the heapify operation starting from the last non-leaf node (index n/2 - 1).

1. Initial array:

   [10, 20, 5, 6, 1, 8]
   

2. Index 2 (Node 5): The left child is 8, and the right child is out of bounds (no child). Since 5 is smaller than 8, no swap is needed.

3. Index 1 (Node 20): The left child is 6, and the right child is 1. The smallest value is 1, so we swap 20 and 1:

   [10, 1, 5, 6, 20, 8]
   

   Now, heapify is applied to the subtree rooted at index 4.

   • Index 4 (Node 20): The left and right children are out of bounds (no children). No further changes.

4. Index 0 (Node 10): The left child is 1, and the right child is 5. The smallest value is 1, so we swap 10 and 1:

   [1, 10, 5, 6, 20, 8]
   

   Now, heapify is applied to the subtree rooted at index 1.

   • Index 1 (Node 10): The left child is 6, and the right child is 8. The smallest value is 6, so we swap 10 and 6:

   [1, 6, 5, 10, 20, 8]
   

   Now, heapify is applied to the subtree rooted at index 3.

   • Index 3 (Node 10): The left and right children are out of bounds (no children). No further changes.

Min-Heap Structure

After these steps, the array represents the following min-heap structure:

        1
       / \
     6    5
    / \  / 
   10  20 8

Min-Heap Properties

1. The shape property is satisfied because the tree is a complete binary tree.
2. The heap property is satisfied because each parent is smaller than or equal to its children.

Heap Operations Examples

1. Insertion (Insert a value):
   Insertion in a heap involves adding an element at the next available position in the tree (i.e., at the end of the array) and then "bubbling up" to restore the heap property.

   Example: Insert 4 into the max-heap [20, 10, 8, 6, 1, 5].

   • Add 4 at the end: [20, 10, 8, 6, 1, 5, 4]
   • Bubble up: Since 4 is less than 6 but greater than 1, no swap is needed, and the heap is valid.

2. Extracting the Root (Extract the max in a max-heap or min in a min-heap):
   Extracting the root removes the root element (max or min) and replaces it with the last element in the heap. Afterward, the heap property is restored by "bubbling down."

   Example: Extract the root from the max-heap [20, 10, 8, 6, 1, 5].

   • Remove 20, replace it with 5: [5, 10, 8, 6, 1]
   • Heapify to restore the heap: Swap 5 with 10 to get [10, 5, 8, 6, 1], and then swap 5 with 6 to get [10, 6, 8, 5, 1].

3. Peek (View the root):
   The peek operation simply returns the root element without modifying the heap. In a max-heap, this will return the maximum value, and in a min-heap, this will return the minimum value.

   Example: For the max-heap [20, 10, 8, 6, 1, 5], the peek operation will return 20.

4. Heapify (Restore the heap property):
   The heapify operation restores the heap property by comparing a node with its children and swapping if necessary. It is applied recursively to ensure that the heap property is maintained.

Use Cases for Heaps

1. Priority Queues:

   • Heaps are commonly used to implement priority queues. For instance, a max-heap can be used to implement a priority queue where the root always holds the highest-priority element, and the next element can be accessed efficiently.

2. Heap Sort:

   • Heap Sort is a comparison-based sorting algorithm that uses a max-heap to extract the