Heap and Priority Queue

Heap and Priority Queue

Description
A heap is a special type of complete binary tree that satisfies the following properties:

  • Min-Heap: The value of each node is less than or equal to the values of its child nodes (the root node is the smallest).
  • Max-Heap: The value of each node is greater than or equal to the values of its child nodes (the root node is the largest).
    Heaps are often used to implement priority queues (a data structure that supports dynamically retrieving the element with the highest/lowest priority). Typical applications include task scheduling, Dijkstra's algorithm, etc.

1. Storage Structure of Heap

Heaps are typically stored using an array, leveraging the properties of a complete binary tree:

  • Root node index is 0 (or 1; here we use 0 as an example).
  • For a node i:
    • Parent node index: (i-1)//2
    • Left child index: 2*i+1
    • Right child index: 2*i+2

Example (Min-Heap):

Array: [1, 3, 6, 5, 9, 8]  
Corresponding tree structure:
      1
    /   \
   3     6
  / \   /
 5   9 8

2. Core Operations of Heap

(1) Insert Element (Sift Up)

Steps:

  1. Add the new element to the end of the array (the last position in the complete binary tree).
  2. Sift Up:
    • Compare the new node's value with its parent's value.
    • If the new node's value is smaller than the parent's (in a min-heap), swap them.
    • Repeat until reaching the root or satisfying the heap property.

Example: Insert 2 into the above heap

Initial heap: [1, 3, 6, 5, 9, 8]  
Insert 2 → [1, 3, 6, 5, 9, 8, 2]  
Sift Up process:
  Parent of 2 is 6 (index 2), 2<6 → swap → [1, 3, 2, 5, 9, 8, 6]  
  Parent of 2 is 3 (index 1), 2<3 → swap → [1, 2, 3, 5, 9, 8, 6]  
  Parent of 2 is 1 (index 0), 2>1 → stop.  
Final heap: [1, 2, 3, 5, 9, 8, 6]

(2) Delete Top Element (Sift Down)

Steps:

  1. Replace the top element with the last element in the array, then remove the last element.
  2. Sift Down:
    • Starting from the root, compare its value with its left and right child nodes.
    • Swap with the child node having the smallest value (in a min-heap).
    • Repeat until reaching a leaf node or satisfying the heap property.

Example: Delete the top element 1

Initial heap: [1, 2, 3, 5, 9, 8, 6]  
Replace top with last element 6 → [6, 2, 3, 5, 9, 8]  
Sift Down process:
  Children of 6 are 2 and 3, smallest child is 2, 6>2 → swap → [2, 6, 3, 5, 9, 8]  
  Children of 6 are 5 and 9, smallest child is 5, 6>5 → swap → [2, 5, 3, 6, 9, 8]  
  6 has no children → stop.  
Final heap: [2, 5, 3, 6, 9, 8]

3. Heap Construction (Heapify)

Quickly construct a heap from an unordered array:

  • Starting from the last non-leaf node (index n//2-1), perform sift down on each node moving backward.
  • Time complexity: O(n) (not O(n log n)).

Example: Build a min-heap from [5, 3, 8, 1, 9]

Steps:
  Non-leaf node index: 5//2-1=1 → start from index 1 (value 3):
    - Index 1: Children of 3 are 1 and 9, smallest child 1<3 → swap → [5, 1, 8, 3, 9]  
  Next index 0 (value 5):
    - Children of 5 are 1 and 8, smallest child 1<5 → swap → [1, 5, 8, 3, 9]  
    - Children of 5 are 3 and 9, smallest child 3<5 → swap → [1, 3, 8, 5, 9]  
Final heap: [1, 3, 8, 5, 9]

4. Implementation of Priority Queue

A heap-based priority queue supports the following operations:

  • push(x): Insert an element (sift up) → O(log n)
  • pop(): Delete the top element (sift down) → O(log n)
  • peek(): Return the top value → O(1)

Application Scenarios:

  • Task scheduling (execution by priority)
  • Merging K sorted lists (taking the smallest node each time)
  • Finding the median of a data stream (two-heap technique)

5. Summary

  • Heaps maintain order through sift up/sift down, ensuring efficient dynamic operations.
  • Priority queues are a typical application of heaps, suitable for scenarios requiring frequent retrieval of extremal values.
  • Note that heap construction time complexity is O(n), which is better than O(n log n) for inserting elements one by one.