Core Heap Operations

To ensure a heap maintains its defining property (min-heap or max-heap) after modifications, we need efficient operations for adding elements, removing the highest-priority element (the root), and constructing a heap from an initial set of elements. These core operations are insert, extract (min or max), and heapify. They rely on restoring the heap property by moving elements up or down the tree structure.

Let's examine how these operations work, typically using a min-heap for illustration. The logic for a max-heap is analogous, simply reversing the comparison criteria (looking for the largest element instead of the smallest).

Inserting an Element

When adding a new element to a heap, we must ensure two things: the structure remains a complete binary tree, and the heap property is preserved.

1. Maintain Structure: Add the new element to the first available spot at the lowest level of the tree. In the common array representation, this simply means appending the element to the end of the array.
2. Restore Heap Property (Sift-Up): The newly added element might violate the heap property. Compare the new element with its parent. If it's smaller than its parent (in a min-heap), swap them. Repeat this comparison and potential swap process, moving the element up the tree (towards the root) until it's either larger than or equal to its parent, or it becomes the new root. This process is often called "sift-up" or "bubble-up".

Consider inserting the value 8 into the following min-heap:

Initial min-heap before insertion.

First, add 8 to the next available position:

Add 8 to the next available position (as a child of 30).

Now, sift-up 8:

• Compare 8 with its parent 30. Since $8 < 30$, swap them.
• Compare 8 with its new parent 20. Since $8 < 20$, swap them.
• Compare 8 with its new parent 10. Since $8 < 10$, swap them.
• 8 is now the root, so the process stops.

Final min-heap after inserting 8 and performing sift-up.

The time complexity for insertion is dominated by the sift-up process. Since a complete binary tree with $n$ elements has a height of $O(\log n)$, the maximum number of swaps needed is proportional to the height. Therefore, insertion takes $O(\log n)$ time.

Extracting the Minimum/Maximum Element

In a min-heap, the smallest element is always at the root. Similarly, the largest element is at the root of a max-heap. Extracting this element requires removing the root and then restoring the heap properties. Let's look at extract-min:

1. Save Root: Store the value of the root node (the minimum value) to be returned.
2. Maintain Structure: Move the last element in the heap (the rightmost element at the lowest level) to the root position. This keeps the tree complete.
3. Restore Heap Property (Sift-Down): The element now at the root might be larger than its children, violating the min-heap property. Compare the new root with its children. If it's larger than either child, swap it with the smaller of its two children. Repeat this comparison and swap process, moving the element down the tree until it's smaller than or equal to both of its children, or it becomes a leaf node. This is known as "sift-down" or "bubble-down".

Let's extract the minimum element (8) from the heap we just created:

Identify the root (8) to extract and the last element (30).

Remove 8, move 30 to the root:

Replace the root with the last element (30).

Now, sift-down 30:

• Compare 30 with its children 10 and 15. The smaller child is 10. Since $30 > 10$, swap 30 with 10.
• 30 is now a child of 10. Compare 30 with its new children 20 and 25. The smaller child is 20. Since $30 > 20$, swap 30 with 20.
• 30 is now a child of 20. It has no children, so it's a leaf. The sift-down process stops.

Final min-heap after extracting the original minimum and performing sift-down.

Similar to insertion, the time complexity for extraction is dominated by the sift-down process, which involves traversing a path from the root to a leaf. This path has length $O(\log n)$, so extraction also takes $O(\log n)$ time.

Building a Heap (Heapify)

Often, we start with an unsorted collection of elements and want to build a heap containing all of them. We could insert each element one by one using the insert operation described above. Since there are $n$ elements and each insertion takes $O(\log n)$ time, this approach takes $O(n \log n)$ time overall.

However, a more efficient method exists, often called heapify or Floyd's algorithm. It works by starting from the last non-leaf node in the tree and applying the sift-down operation to it. Then, it moves backward through the array (or upwards in the tree), applying sift-down to each node until it reaches the root.

Why start from the last non-leaf node? Because all leaf nodes are already valid heaps of size 1. By applying sift-down progressively upwards, we ensure that by the time we process a node, its children are already roots of valid sub-heaps.

Let's heapify the array [30, 20, 15, 10, 25, 18, 17] into a min-heap. The corresponding tree structure initially looks like this (indices shown):

       30 (0)
      /    \
    20(1)  15(2)
   /   \   /   \
 10(3) 25(4) 18(5) 17(6)

The last non-leaf node is at index 2 (value 15). Indices: floor(n/2) - 1 to 0. Here $n=7$, so indices 2, 1, 0.

1. Sift-down node at index 2 (15): Children are 18 and 17. Smaller child is 17. Since $15 < 17$, no swap needed.
2. Sift-down node at index 1 (20): Children are 10 and 25. Smaller child is 10. Since $20 > 10$, swap 20 and 10. 20 is now at index 3 (a leaf), so sift-down stops.

          30 (0)
         /    \
       10(1)  15(2)  <- 20 and 10 swapped
      /   \   /   \
    20(3) 25(4) 18(5) 17(6)
   

3. Sift-down node at index 0 (30): Children are 10 and 15. Smaller child is 10. Since $30 > 10$, swap 30 and 10.

          10 (0)  <- 30 and 10 swapped
         /    \
       30(1)  15(2)
      /   \   /   \
    20(3) 25(4) 18(5) 17(6)
   

   Now 30 is at index 1. Compare 30 with its children 20 and 25. Smaller child is 20. Since $30 > 20$, swap 30 and 20.

          10 (0)
         /    \
       20(1)  15(2) <- 30 and 20 swapped
      /   \   /   \
    30(3) 25(4) 18(5) 17(6)
   

   30 is now at index 3 (a leaf), so sift-down stops.

The final heapified array is [10, 20, 15, 30, 25, 18, 17].

The structure of the min-heap after applying the efficient heapify algorithm.

Although it involves calling sift-down (an $O(\log n)$ operation) roughly $n/2$ times, a more careful analysis shows that the total work done by the heapify algorithm is actually $O(n)$. This is because most nodes are near the bottom of the tree, and sift-down runs much faster for nodes closer to the leaves. Building a heap using this bottom-up approach is significantly faster than repeated insertions for large collections.

These core operations, with their logarithmic time complexities for insertion and extraction and linear time for initial building, make heaps highly efficient for managing prioritized elements, forming the foundation for priority queues.