Heap Operations

Heap Operations

A heap is a binary tree-based data structure that satisfies the heap property. Depending on whether it is a max-heap or min-heap, the heap property states that:

• In a max-heap, the value of each node is greater than or equal to the values of its children (i.e., the largest value is at the root).
• In a min-heap, the value of each node is smaller than or equal to the values of its children (i.e., the smallest value is at the root).

The common operations that can be performed on a heap include insertion, extraction, heapification, and others. Let's break down these operations in detail.

---

1. Insert (Push) Operation

The insert operation adds a new element to the heap while maintaining the heap property.

Steps for Insert Operation:

1. Add the new element at the end of the heap (the next available position in the complete binary tree).
2. Bubble up (or sift up) the new element to restore the heap property by comparing it with its parent. If the new element violates the heap property, it is swapped with its parent.
3. Repeat step 2 until the heap property is restored or the element reaches the root.

Time Complexity:

• O(log n) because, in the worst case, the element may need to bubble up from the leaf to the root.

Insertion Example (Max-Heap):

Suppose we have the following max-heap and we want to insert 15:

Initial max-heap:

        20
       /  \
     15    10
    /  \   /
   8   6  5

• Insert 15 at the end:

        20
       /  \
     15    10
    /  \   /  \
   8   6  5   15
  

• Bubble up 15: Compare it with its parent (10). Since 15 > 10, swap them.

        20
       /  \
     15    15
    /  \   /  \
   8   6  5   10
  

• Bubble up 15: Compare it with its new parent (20). Since 15 < 20, no further action is needed.

Final max-heap:

        20
       /  \
     15    15
    /  \   /  \
   8   6  5   10

---

2. Extract Root (Pop) Operation

The extract root operation removes and returns the root element of the heap (the maximum in a max-heap or the minimum in a min-heap) and then restores the heap property by re-adjusting the remaining elements.

Steps for Extract Root:

1. Swap the root element with the last element in the heap (the rightmost leaf).
2. Remove the last element (which was originally the root).
3. Heapify the root element down to restore the heap property (this involves comparing the root with its children and swapping with the larger (or smaller) child, recursively).
4. Repeat the heapify operation until the heap property is restored.

Time Complexity:

• O(log n) because the heapify operation takes O(log n) time, and it is applied recursively.

Extraction Example (Max-Heap):

Starting with the following max-heap:

        20
       /  \
     15    10
    /  \   /
   8   6  5

• Swap the root (20) with the last element (5):

        5
       /  \
     15    10
    /  \   /
   8   6  20
  

• Remove 20 (the last element).

• Heapify the root (5):

  • Compare 5 with its children (15 and 10), and swap with the larger child (15).

        15
       /  \
     5     10
    /  \   
   8    6 
  

  • Now, compare 5 with its new children (8 and 6). Swap with the larger child (8):

        15
       /  \
     8     10
    /  \   
   5    6 
  

Final max-heap after extraction:

        15
       /  \
     8     10
    /  \   
   5    6 

---

3. Peek Operation (View Root)

The peek operation simply returns the root element of the heap without removing it. This operation is useful when you need to access the maximum (in a max-heap) or minimum (in a min-heap) element, but don't want to modify the heap.

Time Complexity:

• O(1) because it directly accesses the root.

Example:

In the max-heap:

        20
       /  \
     15    10
    /  \   /
   8   6  5

The peek operation will return 20 without altering the heap.

---

4. Heapify Operation

The heapify operation is used to restore the heap property for a subtree rooted at a given index. It is essential in operations like building a heap or extracting the root.

Steps for Heapify (Max-Heap):

1. Compare the node with its children.
2. If the node is smaller than either of its children, swap it with the larger child.
3. Recursively heapify the affected subtree.

Time Complexity:

• O(log n) because the operation works its way down the height of the tree.

Example:

Heapify the subtree rooted at index 0 (root) in the following max-heap:

        5
       /  \
     3    8
    /  \  
   1    6

1. Compare 5 with its children (3 and 8). Since 8 is the largest, swap 5 and 8.

        8
       /  \
     3     5
    /  \   
   1    6
   

2. Now heapify the subtree rooted at index 2 (5). Compare 5 with its children (6), and swap them:

        8
       /  \
     3     6
    /  \   
   1    5
   

Final max-heap after heapify:

        8
       /  \
     3     6
    /  \   
   1    5

---

5. Building a Heap

To convert an unsorted array into a heap, the build heap operation can be used. This process involves calling the heapify operation from the last non-leaf node (index n/2 - 1) down to the root.

Steps for Building a Heap:

1. Start from the last non-leaf node and heapify each node.
2. Move upwards and continue heapifying until the root is reached.

Time Complexity:

• O(n) because, although heapify is O(log n), building a heap only requires O(log n) work for each non-leaf node, and there are approximately n/2 non-leaf nodes. Thus, the total time complexity is linear, O(n).

Example:

Given the array [10, 20, 5, 6, 1, 8], we will build a max-heap.

• Start from index 2 and heapify:

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

  Heapify index 2 (node 5):

  • Compare 5 with 8 (its right child) and swap them:

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

• Move to index 1 and heapify:

  • Compare 20 with its children (6 and 1). No swap is needed because 20 is already the largest.

• Move to index 0 and heapify:

  • Compare 10 with its children (20 and 8). Swap 10 and 20:

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

• Heapify index 1 again:

  • Compare 10 with 6 and 1. Swap 10 with 6:

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

Final max-heap:

        20
       /  \
     6     8
    /  \   /
   10  1  5

---

6. Delete Operation

The delete operation removes a node from the heap. To delete a node, we can:

1. Replace the