Heap Operations: Sift-Up and Sift-Down

1. What is a Heap? The Two Core Properties

A heap is a specialized tree-based data structure that satisfies two crucial properties. Violating either one means it's no longer a valid heap.

Property 1: The Shape Property

A heap must be a complete binary tree. This means that all levels of the tree are completely filled, except possibly for the last level, which is filled from left to right. There are no "gaps" in the tree. This structural constraint is key to a heap's efficient implementation.

Property 2: The Heap Property

This property defines the relationship between a parent node and its children. There are two types of heaps, based on this property:

• Min-Heap: The value of each parent node is less than or equal to the values of its children. This means the smallest element in the entire heap is always at the root.
• Max-Heap: The value of each parent node is greater than or equal to the values of its children. This means the largest element is always at the root.

Throughout this lesson, we will primarily use a min-heap for our examples. The logic for a max-heap is identical, just with the comparisons flipped.

The Array-Based Implementation

Conceptually, a heap is a tree. In practice, however, it's almost always implemented using an array (or a dynamic array/vector). The "complete binary tree" shape property makes this possible and highly efficient.

We can map the tree structure into an array by placing nodes level by level, from left to right. This allows us to find parents and children using simple arithmetic instead of explicit pointers, which is a huge performance and memory win.

Let's watch a short video to see this in action.

As the video explained, for a node at index i (assuming 0-based indexing), we can find its relatives with these formulas:

• Parent: (i - 1) // 2
• Left Child: 2 * i + 1
• Right Child: 2 * i + 2

Now that we have the fundamentals, let's see how we maintain these properties when the heap changes.

2. Core Operations: Sift-Up and Sift-Down

Whenever we add an element to a heap or remove one, we risk violating the heap property. To fix this, we use two essential operations: sift-up and sift-down.

3. Implementing the Core Operations

Let's translate the theory from the article into Python code. We'll build a minimal MinHeap class and implement sift_up and sift_down as internal helper methods. These methods will be the workhorses for the public-facing insert and extract_min methods we'll build in the next lesson.

Sift-Up (for Insertion)

The sift_up operation is used when we insert a new element. The process is:

1. Add the new element to the very end of the array. This maintains the shape property.
2. The new element might be smaller than its parent, violating the heap property.
3. We "sift it up" by repeatedly comparing it to its parent and swapping if it's smaller, until it's in the correct position.

Here is the implementation of sift_up:

class MinHeap:
    def __init__(self):
        self.heap = []

    def _sift_up(self, index):
        # We can't sift up the root. The index must be greater than 0.
        if index == 0:
            return
        
        parent_index = (index - 1) // 2
        
        # If the current node is smaller than its parent, swap them.
        if self.heap[index] < self.heap[parent_index]:
            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
            # Recursively continue sifting up from the new position.
            self._sift_up(parent_index)

Note: A while-loop is often used for an iterative version of this, which avoids recursion depth limits.

Sift-Down (for Extraction)

The sift_down operation is used when we extract the minimum element (the root). The process is:

1. The element to be removed is always the root (heap[0]).
2. To fill the hole at the root and maintain the shape property, we move the last element from the array to the root.
3. This new root is likely out of place, violating the heap property.
4. We "sift it down" by repeatedly comparing it with its children and swapping it with the smallest of its children, until it is smaller than both of its children or becomes a leaf node.

Here is the implementation of sift_down:

class MinHeap:
    # ... (init and _sift_up from before)

    def _sift_down(self, index):
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2
        smallest = index # Assume the current node is the smallest

        # Check if left child exists and is smaller than current smallest
        if left_child_index < len(self.heap) and self.heap[left_child_index] < self.heap[smallest]:
            smallest = left_child_index
            
        # Check if right child exists and is smaller than current smallest
        if right_child_index < len(self.heap) and self.heap[right_child_index] < self.heap[smallest]:
            smallest = right_child_index
            
        # If the smallest element is not the current node, swap them
        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            # Recursively continue sifting down from the new position
            self._sift_down(smallest)

Complexity

Both sift_up and sift_down involve a path from the root to a leaf (or vice-versa). The height of a complete binary tree with $N$ nodes is $O(\log N)$. Therefore, the time complexity for both of these core operations is $O(\log N)$.

Conclusion

Great job! You've just learned the fundamental theory and implementation details of heaps, which are essential for many advanced algorithms and are a frequent topic in technical interviews.

Key Takeaways:

• A heap is defined by two properties: the shape property (it's a complete binary tree) and the heap property (min-heap or max-heap ordering).
• Heaps are almost always implemented with an array for efficiency, using mathematical formulas to navigate the tree structure.
• Sift-up is the $O(\log N)$ operation used to restore the heap property after an insertion by moving an element up the tree.
• Sift-down is the $O(\log N)$ operation used to restore the heap property after an extraction by moving an element down the tree.

In our next lesson, we will use these helper methods to implement a fully functional Priority Queue. We'll see how this data structure can be used to solve a whole new class of problems efficiently.