Principles and Implementation of Binary Heap

Principles and Implementation of Binary Heap

Problem Description
A binary heap is a special type of complete binary tree that satisfies the heap property: the value of each node is greater than or equal to (or less than or equal to) the values of its child nodes. The former is called a max heap, and the latter is called a min heap. Binary heaps are commonly used to implement priority queues, supporting operations such as insertion and deletion of the heap's top element with a time complexity of O(log n). It is required to understand its structural characteristics, storage method, and be able to manually write insertion and deletion operations.

Core Knowledge Points

  1. Complete Binary Tree Property: Except for the last level, all other levels have the maximum number of nodes, and nodes in the last level are aligned to the left.
  2. Heap Property: The value of a parent node is ≥ (or ≤) the values of its child nodes.
  3. Array Storage: Uses array index relationships to simulate the tree structure (indices start from 0 or 1).
  4. Sift Up and Sift Down: The core operations for maintaining the heap property.

Detailed Problem-Solving Process

Step 1: Understand the Storage Structure of a Binary Heap

  • Use an array to store the complete binary tree, saving pointer space.
  • Index Relationships (assuming indices start from 0):
    • Parent node index: parent(i) = (i - 1) // 2
    • Left child index: left_child(i) = 2*i + 1
    • Right child index: right_child(i) = 2*i + 2
  • Example: Array [10, 7, 8, 5, 3] corresponds to the following max heap: 
          10
     /  \
    7    8
   / \
  5   3

Step 2: Insertion Operation and Sift Up
Objective: Insert a new element at the end of the heap and adjust it to the correct position by sifting up.
Procedure:

  1. Append the new element to the end of the array (end of the heap).
  2. Compare the value of the new element with its parent node:
    • If it's a max heap and the new element's value > the parent's value, swap their positions.
    • Repeat Step 2 until the new element's value ≤ the parent's value or the root is reached.

Example: Insert element 9 into the max heap [10, 7, 8, 5, 3]:

  • Initial: [10, 7, 8, 5, 3, 9] → 9's parent is 3 (index 2), 9 > 3, swap → [10, 7, 8, 5, 9, 3]
  • Continue: 9's parent is 7 (index 1), 9 > 7, swap → [10, 9, 8, 5, 7, 3]
  • Continue: 9's parent is 10 (index 0), 9 ≤ 10, stop. Final heap: [10, 9, 8, 5, 7, 3].

Step 3: Deletion of the Heap Top and Sift Down
Objective: After deleting the top element, move the last element of the heap to the top and adjust it to the correct position by sifting down.
Procedure:

  1. Replace the top element with the last element of the heap, then remove the last element.
  2. Starting from the top, compare the current node's value with its children's values:
    • For a max heap, select the child with the larger value.
    • If the current node's value < the child's value, swap their positions.
  3. Repeat Step 2 until the current node's value ≥ the child's value or it becomes a leaf node.

Example: Delete the top element 10 from the max heap [10, 9, 8, 5, 7, 3]:

  • Replace the top with the last element 3: [3, 9, 8, 5, 7]
  • Sift down: Compare 3 with its children 9 and 8, 9 is larger, 3 < 9, swap → [9, 3, 8, 5, 7]
  • Continue: Compare 3 with its children 5 and 7, 7 is larger, 3 < 7, swap → [9, 7, 8, 5, 3]
  • Continue: 3 has no children, stop. Final heap: [9, 7, 8, 5, 3].

Step 4: Code Implementation (Max Heap)

class MaxHeap:
    def __init__(self):
        self.heap = []
    
    def insert(self, val):
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)
    
    def pop_max(self):
        if not self.heap:
            return None
        max_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self._sift_down(0)
        return max_val
    
    def _sift_up(self, idx):
        while idx > 0:
            parent = (idx - 1) // 2
            if self.heap[idx] <= self.heap[parent]:
                break
            self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx]
            idx = parent
    
    def _sift_down(self, idx):
        n = len(self.heap)
        while idx * 2 + 1 < n:  # At least has a left child
            left = idx * 2 + 1
            right = idx * 2 + 2
            max_child = left
            if right < n and self.heap[right] > self.heap[left]:
                max_child = right
            if self.heap[idx] >= self.heap[max_child]:
                break
            self.heap[idx], self.heap[max_child] = self.heap[max_child], self.heap[idx]
            idx = max_child

Key Points Summary

  • Sift Up is used for insertion, adjusting from the bottom up.
  • Sift Down is used for deleting the top element, adjusting from the top down.
  • Time complexity: Both insertion and deletion are O(log n); building a heap is O(n) (by constructing from bottom up).
  • Application scenarios: Priority queues, Top K problems, heap sort, etc.