Heap Sort — Sắp xếp vun đống

std::sort() trong C++ STL thực chất là introsort — hybrid giữa Quick Sort, Heap Sort, và Insertion Sort. Khi Quick Sort đệ quy quá sâu (vượt 2 × log₂(n) tầng), introsort lập tức chuyển sang Heap Sort để đảm bảo O(n log n) worst case. Đây không phải thuật toán "dự phòng" — đây là lưới an toàn ngăn production system rơi vào O(n²).

Heap Sort là thuật toán duy nhất đạt đồng thời ba tiêu chí: O(n log n) worst case, O(1) auxiliary space, và không cần đệ quy bắt buộc. Merge Sort đạt O(n log n) nhưng cần O(n) bộ nhớ phụ. Quick Sort dùng O(1) space nhưng worst case O(n²). Heap Sort là lựa chọn duy nhất khi bạn cần cả hai đảm bảo cùng lúc.

Nhưng giá trị của Heap Sort vượt xa việc sắp xếp. Hiểu cấu trúc heap mở khóa priority queue — cấu trúc dữ liệu cốt lõi trong thuật toán Dijkstra (tìm đường ngắn nhất), Huffman coding (nén dữ liệu), A* search (game AI), job scheduling (hệ điều hành), và mọi hệ thống event-driven.

Bức tranh tư duy

Hình dung một giải đấu loại trực tiếp (single-elimination tournament) với 8 đội bóng. Mỗi cặp đấu, đội mạnh hơn thắng và tiến lên vòng tiếp theo. Sau 3 vòng (log₂8), đội vô địch — mạnh nhất — đứng ở đỉnh.

Binary heap hoạt động chính xác như cây giải đấu này: mỗi node cha "mạnh hơn" (lớn hơn trong max-heap) hai node con. Gốc cây luôn là phần tử lớn nhất.

text

Max-Heap (biểu diễn cây):

                    90
                 /      \
              80          70
            /    \      /    \
          50      60  30      20
         /  \
       10    40

Biểu diễn mảng (0-indexed):
Index:  [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]
Value:   90   80   70   50   60   30   20   10   40

Quan hệ cha-con (0-indexed):
  Cha của node i     = (i - 1) / 2
  Con trái của node i = 2 * i + 1
  Con phải của node i = 2 * i + 2

Tính chất max-heap: arr[parent] ≥ arr[child] với mọi node

Thuật toán Heap Sort diễn ra hai pha:

Build Max-Heap: Biến mảng hỗn loạn thành cây giải đấu — đội mạnh nhất lên đỉnh.
Extract lần lượt: Lấy nhà vô địch ra (swap với phần tử cuối), thu nhỏ giải đấu, tổ chức lại vòng loại cho phần còn lại. Lặp lại cho đến khi hết.

📌 Khi nào analogy bị phá vỡ

Trong giải đấu thật, khi nhà vô địch rời đi, đội thua ở trận chung kết tự động lên ngôi. Nhưng trong heap, phần tử cuối mảng (đội "yếu nhất") được đẩy lên gốc, rồi phải sift-down (thi đấu lại từ đầu) để tìm vị trí đúng. Đây là chi phí O(log n) cho mỗi lần extract.

Cốt lõi kỹ thuật

Binary Heap — cấu trúc nền tảng

Binary heap là complete binary tree (cây nhị phân đầy đủ) được lưu trữ trong mảng phẳng. "Complete" nghĩa là mọi tầng đều đầy, ngoại trừ tầng cuối được lấp từ trái sang phải. Đặc tính này cho phép biểu diễn cây bằng mảng mà không cần pointer.

Có hai loại heap:

Loại	Tính chất	Ứng dụng
Max-heap	`arr[parent] ≥ arr[child]`	Heap Sort, tìm max nhanh
Min-heap	`arr[parent] ≤ arr[child]`	Priority queue (Dijkstra), tìm min nhanh

Heap Sort sử dụng max-heap để sort tăng dần: phần tử lớn nhất luôn ở gốc arr[0], được swap về cuối mảng mỗi vòng.

Sift-Down (Heapify) — thao tác cốt lõi

Sift-down nhận một node i và đẩy nó xuống đúng vị trí trong heap. Tại mỗi bước, so sánh node với hai con, swap với con lớn hơn nếu vi phạm tính chất heap, rồi tiếp tục đệ quy xuống.

text

Sift-down node 0 (giá trị 10) trong heap [10, 80, 70, 50, 60]:

Bước 1: 10 < max(80, 70) = 80 → swap(10, 80)
         80                10 → 80
        / \       →       / \
      10   70           80   70       (tiếp tục tại vị trí 1)
     / \               / \
   50   60           50   60

Bước 2: 10 < max(50, 60) = 60 → swap(10, 60)
         80                80
        / \       →       / \
      10   70           60   70
     / \               / \
   50   60           50   10         ✓ heap hợp lệ

Tổng: 2 swap = O(log n) cho cây cao log₂(n)

C++PythonJavaGo

cpp

#include <algorithm>

void siftDown(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        siftDown(arr, n, largest);
    }
}

python

def sift_down(arr: list[int], n: int, i: int) -> None:
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        sift_down(arr, n, largest)

java

public class HeapSort {
    static void siftDown(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;

        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            siftDown(arr, n, largest);
        }
    }
}

package sorting

func siftDown(arr []int, n, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2

    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }

    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        siftDown(arr, n, largest)
    }
}

Sift-Up vs Sift-Down — hai hướng khác nhau

Thao tác	Hướng di chuyển	Khi nào dùng	Độ phức tạp
Sift-Down	Từ node xuống lá	Build heap, extract max	O(log n)
Sift-Up	Từ lá lên gốc	Insert phần tử mới vào heap	O(log n)

Sift-down dùng trong Heap Sort vì build-heap bằng sift-down đạt O(n), trong khi build bằng sift-up chỉ đạt O(n log n). Lý do: các node ở tầng thấp (gần lá) chiếm đa số — sift-down từ chúng chỉ đi vài bước, còn sift-up phải đi đến gốc.

Build Heap — O(n) chứ không phải O(n log n)

Build heap gọi sift-down cho mỗi node không phải lá, bắt đầu từ node nội cuối cùng (n/2 - 1) ngược về gốc (0). Các lá (chiếm ~n/2 node) đã là heap hợp lệ nên bỏ qua.

Chứng minh O(n): cây nhị phân đầy đủ có ~n/2 lá (sift-down 0 bước), ~n/4 node tầng kế (1 bước), ~n/8 node (2 bước)... Tổng công việc:

text

Σ = n/4 × 1 + n/8 × 2 + n/16 × 3 + ... = n × Σ(k/2^(k+1)) = n × 1 = O(n)

Đây là kết quả phản trực giác — xây dựng heap từ mảng bất kỳ chỉ tốn thời gian tuyến tính.

Thuật toán Heap Sort hoàn chỉnh

Hai pha:

Build max-heap từ mảng input — O(n)
Extract max lặp lại n−1 lần: swap gốc với phần tử cuối, giảm heap size, sift-down gốc — mỗi lần O(log n)

Tổng: O(n) + O(n log n) = O(n log n).

C++PythonJavaGo

cpp

#include <algorithm>

void siftDown(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        siftDown(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // Pha 1: Build max-heap — O(n)
    for (int i = n / 2 - 1; i >= 0; i--)
        siftDown(arr, n, i);

    // Pha 2: Extract max lần lượt — O(n log n)
    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        siftDown(arr, i, 0);
    }
}

python

def sift_down(arr: list[int], n: int, i: int) -> None:
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        sift_down(arr, n, largest)


def heap_sort(arr: list[int]) -> None:
    n = len(arr)

    # Pha 1: Build max-heap — O(n)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)

    # Pha 2: Extract max lần lượt — O(n log n)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        sift_down(arr, i, 0)

java

public class HeapSort {
    static void siftDown(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;

        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            siftDown(arr, n, largest);
        }
    }

    public static void heapSort(int[] arr) {
        int n = arr.length;

        // Pha 1: Build max-heap — O(n)
        for (int i = n / 2 - 1; i >= 0; i--)
            siftDown(arr, n, i);

        // Pha 2: Extract max lần lượt — O(n log n)
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            siftDown(arr, i, 0);
        }
    }
}

package sorting

func siftDown(arr []int, n, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2

    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }

    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        siftDown(arr, n, largest)
    }
}

func HeapSort(arr []int) {
    n := len(arr)

    // Pha 1: Build max-heap — O(n)
    for i := n/2 - 1; i >= 0; i-- {
        siftDown(arr, n, i)
    }

    // Pha 2: Extract max lần lượt — O(n log n)
    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        siftDown(arr, i, 0)
    }
}

Thực chiến

Tình huống 1: Priority Queue — hàng đợi ưu tiên

Bối cảnh: Hệ thống task scheduler cần lấy task có priority cao nhất trong O(1), thêm task mới trong O(log n). Mảng sorted cho phép lấy max O(1) nhưng insert là O(n). Linked list cho insert O(1) nhưng tìm max O(n). Binary heap giải quyết cả hai trong O(log n).

Mục tiêu: Cài đặt max-priority queue với ba thao tác: push, pop (lấy phần tử lớn nhất), peek.

C++PythonJavaGo

cpp

#include <vector>
#include <stdexcept>

class MaxPriorityQueue {
    std::vector<int> heap;

    void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[parent] >= heap[i]) break;
            std::swap(heap[parent], heap[i]);
            i = parent;
        }
    }

    void siftDown(int i) {
        int n = heap.size();
        while (true) {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < n && heap[left] > heap[largest]) largest = left;
            if (right < n && heap[right] > heap[largest]) largest = right;
            if (largest == i) break;
            std::swap(heap[i], heap[largest]);
            i = largest;
        }
    }

public:
    void push(int val) {
        heap.push_back(val);
        siftUp(heap.size() - 1);
    }

    int pop() {
        if (heap.empty()) throw std::runtime_error("Heap is empty");
        int top = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) siftDown(0);
        return top;
    }

    int peek() const {
        if (heap.empty()) throw std::runtime_error("Heap is empty");
        return heap[0];
    }

    bool empty() const { return heap.empty(); }
};

python

class MaxPriorityQueue:
    def __init__(self):
        self._heap: list[int] = []

    def _sift_up(self, i: int) -> None:
        while i > 0:
            parent = (i - 1) // 2
            if self._heap[parent] >= self._heap[i]:
                break
            self._heap[parent], self._heap[i] = self._heap[i], self._heap[parent]
            i = parent

    def _sift_down(self, i: int) -> None:
        n = len(self._heap)
        while True:
            largest = i
            left, right = 2 * i + 1, 2 * i + 2
            if left < n and self._heap[left] > self._heap[largest]:
                largest = left
            if right < n and self._heap[right] > self._heap[largest]:
                largest = right
            if largest == i:
                break
            self._heap[i], self._heap[largest] = self._heap[largest], self._heap[i]
            i = largest

    def push(self, val: int) -> None:
        self._heap.append(val)
        self._sift_up(len(self._heap) - 1)

    def pop(self) -> int:
        if not self._heap:
            raise IndexError("Heap is empty")
        top = self._heap[0]
        self._heap[0] = self._heap[-1]
        self._heap.pop()
        if self._heap:
            self._sift_down(0)
        return top

    def peek(self) -> int:
        if not self._heap:
            raise IndexError("Heap is empty")
        return self._heap[0]

java

import java.util.ArrayList;
import java.util.NoSuchElementException;

public class MaxPriorityQueue {
    private final ArrayList<Integer> heap = new ArrayList<>();

    private void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap.get(parent) >= heap.get(i)) break;
            swap(parent, i);
            i = parent;
        }
    }

    private void siftDown(int i) {
        int n = heap.size();
        while (true) {
            int largest = i, left = 2 * i + 1, right = 2 * i + 2;
            if (left < n && heap.get(left) > heap.get(largest)) largest = left;
            if (right < n && heap.get(right) > heap.get(largest)) largest = right;
            if (largest == i) break;
            swap(i, largest);
            i = largest;
        }
    }

    private void swap(int a, int b) {
        int temp = heap.get(a);
        heap.set(a, heap.get(b));
        heap.set(b, temp);
    }

    public void push(int val) {
        heap.add(val);
        siftUp(heap.size() - 1);
    }

    public int pop() {
        if (heap.isEmpty()) throw new NoSuchElementException("Heap is empty");
        int top = heap.get(0);
        heap.set(0, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) siftDown(0);
        return top;
    }

    public int peek() {
        if (heap.isEmpty()) throw new NoSuchElementException("Heap is empty");
        return heap.get(0);
    }
}

package sorting

import "errors"

type MaxPriorityQueue struct {
    heap []int
}

func (pq *MaxPriorityQueue) siftUp(i int) {
    for i > 0 {
        parent := (i - 1) / 2
        if pq.heap[parent] >= pq.heap[i] {
            break
        }
        pq.heap[parent], pq.heap[i] = pq.heap[i], pq.heap[parent]
        i = parent
    }
}

func (pq *MaxPriorityQueue) siftDown(i int) {
    n := len(pq.heap)
    for {
        largest := i
        left, right := 2*i+1, 2*i+2
        if left < n && pq.heap[left] > pq.heap[largest] {
            largest = left
        }
        if right < n && pq.heap[right] > pq.heap[largest] {
            largest = right
        }
        if largest == i {
            break
        }
        pq.heap[i], pq.heap[largest] = pq.heap[largest], pq.heap[i]
        i = largest
    }
}

func (pq *MaxPriorityQueue) Push(val int) {
    pq.heap = append(pq.heap, val)
    pq.siftUp(len(pq.heap) - 1)
}

func (pq *MaxPriorityQueue) Pop() (int, error) {
    if len(pq.heap) == 0 {
        return 0, errors.New("heap is empty")
    }
    top := pq.heap[0]
    pq.heap[0] = pq.heap[len(pq.heap)-1]
    pq.heap = pq.heap[:len(pq.heap)-1]
    if len(pq.heap) > 0 {
        pq.siftDown(0)
    }
    return top, nil
}

func (pq *MaxPriorityQueue) Peek() (int, error) {
    if len(pq.heap) == 0 {
        return 0, errors.New("heap is empty")
    }
    return pq.heap[0], nil
}

Phân tích:

push: O(log n) — sift-up từ lá lên gốc
pop: O(log n) — swap gốc với cuối, sift-down gốc mới
peek: O(1) — gốc luôn là max
Space: O(n) cho mảng lưu trữ, không cần pointer như BST

Tình huống 2: Top-K Elements — tìm k phần tử lớn nhất

Bối cảnh: Hệ thống analytics cần tìm 10 sản phẩm bán chạy nhất từ 50 triệu giao dịch. Sort toàn bộ mất O(n log n). Dùng min-heap kích thước k chỉ cần O(n log k) — với k = 10 và n = 50 triệu, tiết kiệm ~6× thời gian.

Chiến thuật: Duy trì min-heap kích thước k. Duyệt qua từng phần tử: nếu lớn hơn gốc heap (phần tử nhỏ nhất trong top-k hiện tại), thay thế gốc và sift-down. Kết thúc, heap chứa đúng k phần tử lớn nhất.

PythonC++JavaGo

python

import heapq

def top_k_elements(nums: list[int], k: int) -> list[int]:
    """Tìm k phần tử lớn nhất — O(n log k) time, O(k) space."""
    if k >= len(nums):
        return sorted(nums, reverse=True)

    # heapq là min-heap: giữ k phần tử lớn nhất
    min_heap = nums[:k]
    heapq.heapify(min_heap)  # O(k)

    for num in nums[k:]:
        if num > min_heap[0]:
            heapq.heapreplace(min_heap, num)  # O(log k)

    return sorted(min_heap, reverse=True)

cpp

#include <vector>
#include <queue>
#include <algorithm>

std::vector<int> topKElements(const std::vector<int>& nums, int k) {
    // Min-heap: giữ k phần tử lớn nhất
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    for (int num : nums) {
        minHeap.push(num);
        if (static_cast<int>(minHeap.size()) > k) {
            minHeap.pop();  // loại phần tử nhỏ nhất
        }
    }

    std::vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    std::sort(result.rbegin(), result.rend());
    return result;
}

java

import java.util.*;

public class TopK {
    public static List<Integer> topKElements(int[] nums, int k) {
        // Min-heap: giữ k phần tử lớn nhất
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        List<Integer> result = new ArrayList<>(minHeap);
        result.sort(Collections.reverseOrder());
        return result;
    }
}

package sorting

import (
    "container/heap"
    "sort"
)

type IntMinHeap []int

func (h IntMinHeap) Len() int            { return len(h) }
func (h IntMinHeap) Less(i, j int) bool   { return h[i] < h[j] }
func (h IntMinHeap) Swap(i, j int)        { h[i], h[j] = h[j], h[i] }
func (h *IntMinHeap) Push(x interface{})  { *h = append(*h, x.(int)) }
func (h *IntMinHeap) Pop() interface{} {
    old := *h
    val := old[len(old)-1]
    *h = old[:len(old)-1]
    return val
}

func TopKElements(nums []int, k int) []int {
    h := &IntMinHeap{}
    heap.Init(h)

    for _, num := range nums {
        heap.Push(h, num)
        if h.Len() > k {
            heap.Pop(h)
        }
    }

    result := []int(*h)
    sort.Sort(sort.Reverse(sort.IntSlice(result)))
    return result
}

Phân tích:

Time: O(n log k) — mỗi phần tử tốn O(log k) cho heap operation
Space: O(k) — chỉ giữ k phần tử trong heap
Với k << n, hiệu quả hơn nhiều so với sort toàn bộ O(n log n)

Tình huống 3: Introsort — Heap Sort làm fallback trong production

C++ STL std::sort() dùng introsort với cơ chế:

Bắt đầu bằng Quick Sort (median-of-three pivot)
Nếu recursion depth vượt 2 × log₂(n) → chuyển sang Heap Sort
Khi mảng con ≤ 16 phần tử → chuyển sang Insertion Sort

Heap Sort được chọn làm fallback vì: O(n log n) worst case đảm bảo, O(1) auxiliary space (không cần mảng tạm như Merge Sort), và đơn giản để tích hợp (chỉ cần gọi trên mảng con hiện tại). Đây là lý do std::sort() đạt O(n log n) worst case mà vẫn nhanh như Quick Sort trên average case.

Sai lầm điển hình

❌ Sai lầm 1: Sift-down sai hướng — heapify từ gốc xuống khi build heap

Vấn đề: Gọi sift-down từ gốc (index 0) xuống, duyệt thuận i = 0 đến n/2 - 1.

python

# SAI: duyệt thuận từ gốc xuống
for i in range(n // 2):
    sift_down(arr, n, i)

Tại sao sai: Sift-down đẩy một node xuống vị trí đúng, nhưng nó giả định cây con bên dưới đã là heap hợp lệ. Nếu duyệt từ gốc xuống, khi xử lý node i, các con của nó chưa được heapify → kết quả không phải heap hợp lệ. Bug này đặc biệt nguy hiểm vì mảng "trông có vẻ gần đúng" nhưng sai ở các trường hợp cụ thể.

python

# ĐÚNG: duyệt ngược từ node nội cuối cùng lên gốc
for i in range(n // 2 - 1, -1, -1):
    sift_down(arr, n, i)

Build heap phải đi từ dưới lên trên — đảm bảo khi xử lý mỗi node, toàn bộ cây con phía dưới đã là heap hợp lệ.

❌ Sai lầm 2: Nghĩ build-heap là O(n log n)

Vấn đề: Phân tích "n node × O(log n) sift-down mỗi node = O(n log n)".

Tại sao sai: Phân tích này quá thô. Thực tế, đa số node nằm gần lá và sift-down rất ít bước:

~n/2 lá: 0 bước (bỏ qua)
~n/4 node tầng kế: tối đa 1 bước
~n/8 node: tối đa 2 bước
Chỉ 1 gốc: tối đa log n bước

Tổng = n/4 × 1 + n/8 × 2 + n/16 × 3 + ... ≤ n × Σ(k/2^(k+1)) = O(n). Hiểu đúng điều này là dấu hiệu bạn thực sự hiểu heap, không chỉ nhớ công thức.

❌ Sai lầm 3: Mặc định Heap Sort là stable

Vấn đề: Dùng Heap Sort khi cần giữ thứ tự tương đối của các phần tử bằng nhau.

text

Input:  [(5,'a'), (3,'x'), (5,'b'), (1,'y')]
Mong đợi stable: [(1,'y'), (3,'x'), (5,'a'), (5,'b')]  ← giữ 'a' trước 'b'
Heap Sort thực tế: có thể cho [(1,'y'), (3,'x'), (5,'b'), (5,'a')]  ← đảo!

Tại sao sai: Trong pha extract-max, phần tử cuối mảng (vị trí ngẫu nhiên) được swap lên gốc rồi sift-down. Quá trình này phá vỡ thứ tự tương đối ban đầu. Heap Sort là unstable sort — nếu cần stability, dùng Merge Sort hoặc Timsort.

❌ Sai lầm 4: Nhầm index 0-based và 1-based

Vấn đề: Nhiều giáo trình dùng index bắt đầu từ 1 (thuận tiện cho toán: con trái = 2i, con phải = 2i + 1). Nhưng mảng trong hầu hết ngôn ngữ bắt đầu từ 0.

python

# SAI: dùng công thức 1-based trên mảng 0-based
left = 2 * i        # Thực ra là con trái khi index từ 1
right = 2 * i + 1   # Thực ra là con phải khi index từ 1

python

# ĐÚNG: công thức 0-based
left = 2 * i + 1
right = 2 * i + 2
parent = (i - 1) // 2

Chỉ số	0-based	1-based
Con trái	`2i + 1`	`2i`
Con phải	`2i + 2`	`2i + 1`
Cha	`(i - 1) / 2`	`i / 2`
Node nội cuối	`n/2 - 1`	`n/2`

Khi tham khảo tài liệu, luôn kiểm tra convention trước khi code. Bug này gây lệch toàn bộ cây — kết quả sort sai nhưng không crash, rất khó debug.

Under the Hood

Hiệu năng

Trường hợp	Time	Space	Ghi chú
Best case	O(n log n)	O(1)	Mảng đã sorted — vẫn phải build heap + extract
Average case	O(n log n)	O(1)	Không phụ thuộc vào phân bố input
Worst case	O(n log n)	O(1)	Đảm bảo — không có kịch bản suy giảm
Build heap	O(n)	O(1)	Chỉ pha đầu tiên

Heap Sort luôn thực hiện đúng cùng một số bước bất kể input — không có "best case nhanh hơn" như Insertion Sort hay "worst case chậm hơn" như Quick Sort. Đây vừa là ưu điểm (predictable) vừa là nhược điểm (không tận dụng được input đã gần sorted).

Tại sao Heap Sort thua Quick Sort trong thực tế

Trên paper, Heap Sort đáng ra phải thắng — O(n log n) đảm bảo, O(1) space. Nhưng benchmark thực tế cho thấy Quick Sort nhanh hơn 2-5× trên hầu hết input. Nguyên nhân: cache locality.

text

Quick Sort — truy cập tuần tự:
Partition quét mảng từ trái → phải: arr[0], arr[1], arr[2], ...
→ CPU cache line (64 bytes = 16 integers) được tận dụng tối đa
→ Cache hit rate: ~95%

Heap Sort — truy cập nhảy cóc:
Sift-down từ node i: so sánh arr[i], arr[2i+1], arr[2i+2]
Rồi nhảy sang arr[4i+3], arr[4i+4], arr[8i+7]...
→ Mỗi tầng nhân đôi khoảng cách trong mảng
→ Cache hit rate: ~50-70% (tệ hơn đáng kể)

Với mảng 1 triệu integers (4 MB), sift-down từ gốc nhảy qua ~20 tầng, mỗi bước có thể truy cập vùng nhớ cách nhau hàng trăm KB — gần như chắc chắn cache miss.

So sánh ba thuật toán O(n log n)

Tiêu chí	Heap Sort	Merge Sort	Quick Sort
Worst case	O(n log n) ✅	O(n log n) ✅	O(n²) ❌
Average case	O(n log n)	O(n log n)	O(n log n)
Space	O(1) ✅	O(n) ❌	O(log n)
Stable	❌	✅	❌
Cache-friendly	❌	Trung bình	✅
Adaptive	❌	❌	Trung bình
Tốc độ thực tế	Chậm nhất	Trung bình	Nhanh nhất
Use case chính	Fallback (introsort), embedded	External sort, stable sort	General-purpose

Trade-offs

Khi nào NÊN dùng Heap Sort: Hệ thống cần worst-case guarantee (real-time, embedded), bộ nhớ phụ bị giới hạn nghiêm ngặt, làm fallback trong introsort, hoặc khi cần partial sort (extract top-k bằng heap hiệu quả hơn sort toàn bộ).

Khi nào KHÔNG NÊN dùng: General-purpose sorting (Quick Sort/introsort tốt hơn), cần stable sort (dùng Merge Sort/Timsort), dữ liệu gần sorted (Timsort tối ưu hơn nhiều), dataset nhỏ (Insertion Sort nhanh hơn).

Checklist ghi nhớ

✅ Checklist triển khai

Cấu trúc heap

[ ] Binary heap là complete binary tree lưu trong mảng phẳng
[ ] Max-heap: arr[parent] ≥ arr[child] — gốc luôn là phần tử lớn nhất
[ ] Công thức 0-based: con trái 2i + 1, con phải 2i + 2, cha (i - 1) / 2

Thao tác cốt lõi

[ ] Sift-down: đẩy node xuống đúng vị trí — dùng trong build heap và extract
[ ] Sift-up: đẩy node lên đúng vị trí — dùng khi insert phần tử mới
[ ] Build heap bằng sift-down ngược từ dưới lên — O(n), không phải O(n log n)

Thuật toán Heap Sort

[ ] Pha 1: Build max-heap — O(n)
[ ] Pha 2: Lặp n − 1 lần: swap gốc với cuối, giảm heap size, sift-down — O(n log n)

Tính chất quan trọng

[ ] Luôn O(n log n) — best, average, worst case không khác nhau
[ ] In-place O(1) auxiliary space — không cần mảng tạm
[ ] Không stable — không giữ thứ tự tương đối phần tử bằng nhau
[ ] Cache-unfriendly — truy cập nhảy cóc trong mảng, thua Quick Sort trong thực tế

Bài tập luyện tập

Bài 1: Tìm k phần tử nhỏ nhất — Foundation

Đề bài: Cho mảng nums và số nguyên k, trả về danh sách k phần tử nhỏ nhất theo thứ tự tăng dần. Không được sort toàn bộ mảng. Yêu cầu: Time O(n log k), Space O(k).

Input: nums = [7, 10, 4, 3, 20, 15], k = 3Output: [3, 4, 7]

🧠 Quiz

Build-heap trên mảng n phần tử có độ phức tạp thời gian là bao nhiêu?

[ ] A. O(n log n) — vì gọi sift-down n/2 lần, mỗi lần O(log n)
[x] B. O(n) — vì đa số node gần lá và sift-down rất ít bước
[ ] C. O(n²) — vì cần so sánh mọi cặp phần tử
[ ] D. O(log n) — vì cây có chiều cao log n

Giải thích: Đáp án A là phân tích quá thô. Thực tế, ~n/2 lá không cần xử lý, ~n/4 node chỉ sift 1 bước, ~n/8 node sift 2 bước... Tổng chuỗi hội tụ về O(n). Đây là kết quả phản trực giác nhưng đã được chứng minh chặt chẽ.

💡 Gợi ý

Dùng max-heap kích thước k (không phải min-heap).
Duyệt qua mảng: nếu phần tử hiện tại nhỏ hơn gốc max-heap (phần tử lớn nhất trong k ứng viên), thay thế gốc và sift-down.
Kết thúc, max-heap chứa k phần tử nhỏ nhất. Sort kết quả nếu cần thứ tự.

✅ Lời giải

python

import heapq

def k_smallest(nums: list[int], k: int) -> list[int]:
    if k >= len(nums):
        return sorted(nums)

    # Max-heap trick: negate values vì Python chỉ có min-heap
    max_heap = [-x for x in nums[:k]]
    heapq.heapify(max_heap)  # O(k)

    for num in nums[k:]:
        if num < -max_heap[0]:  # nhỏ hơn phần tử lớn nhất trong heap
            heapq.heapreplace(max_heap, -num)  # O(log k)

    result = sorted([-x for x in max_heap])
    return result

Phân tích: Time O(n log k) — duyệt n phần tử, mỗi heap operation O(log k). Space O(k). Với k = 10 và n = 10⁷, chỉ cần ~10⁷ × 3.3 ≈ 3.3 × 10⁷ operations thay vì ~10⁷ × 23 ≈ 2.3 × 10⁸ nếu sort toàn bộ.

Bài 2: Heap Sort iterative (không đệ quy) — Intermediate

Đề bài: Cài đặt Heap Sort hoàn chỉnh với sift-down không dùng đệ quy (iterative). Mục đích: tránh stack overflow trên mảng cực lớn và hiểu rõ cơ chế sift-down. Trả về mảng đã sort tại chỗ.

Input: [12, 11, 13, 5, 6, 7]Output: [5, 6, 7, 11, 12, 13]

💡 Gợi ý

Thay vì gọi đệ quy sift_down(arr, n, largest), dùng vòng while và cập nhật i = largest mỗi vòng.
Điều kiện dừng: khi largest == i (node đã ở đúng vị trí) hoặc khi node là lá.
Phần còn lại (build heap + extract) giữ nguyên.

✅ Lời giải

python

def sift_down_iterative(arr: list[int], n: int, i: int) -> None:
    while True:
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2

        if left < n and arr[left] > arr[largest]:
            largest = left
        if right < n and arr[right] > arr[largest]:
            largest = right

        if largest == i:
            break

        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest


def heap_sort_iterative(arr: list[int]) -> None:
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        sift_down_iterative(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        sift_down_iterative(arr, i, 0)

Phân tích: Time O(n log n) — giống bản đệ quy. Space O(1) thực sự — không có stack frame đệ quy. Bản iterative được ưu tiên trong production vì: (1) không rủi ro stack overflow với n lớn, (2) dễ tối ưu bởi compiler (loop unrolling), (3) sift-down chỉ đi theo một nhánh nên chuyển thành loop rất tự nhiên.

🧠 Quiz

Heap Sort có phải là stable sort không?

[ ] A. Có — vì phần tử bằng nhau không bao giờ bị swap
[ ] B. Có — vì binary heap giữ thứ tự insert
[x] C. Không — pha extract-max swap phần tử cuối lên gốc, phá vỡ thứ tự tương đối
[ ] D. Tùy thuộc vào cách cài đặt sift-down

Giải thích: Khi extract max, phần tử cuối mảng (vị trí "ngẫu nhiên" trong heap) được swap lên gốc rồi sift-down. Quá trình này hoàn toàn không quan tâm đến thứ tự ban đầu của các phần tử bằng nhau. Đáp án D sai vì không có cách cài đặt sift-down nào biến Heap Sort thành stable mà không thay đổi bản chất thuật toán.

Liên kết học tiếp

Từ khóa glossary: heap sort, sắp xếp vun đống, binary heap, max-heap, min-heap, priority queue, heapify, sift-down, sift-up, complete binary tree

Tìm kiếm liên quan: sắp xếp vun đống, heap sort là gì, priority queue cài đặt, so sánh heap sort quick sort, binary heap trong mảng

Heap Sort — Sắp xếp vun đống ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Binary Heap — cấu trúc nền tảng ​

Sift-Down (Heapify) — thao tác cốt lõi ​

Sift-Up vs Sift-Down — hai hướng khác nhau ​

Build Heap — O(n) chứ không phải O(n log n) ​

Thuật toán Heap Sort hoàn chỉnh ​

Thực chiến ​

Tình huống 1: Priority Queue — hàng đợi ưu tiên ​

Tình huống 2: Top-K Elements — tìm k phần tử lớn nhất ​

Tình huống 3: Introsort — Heap Sort làm fallback trong production ​

Sai lầm điển hình ​

❌ Sai lầm 1: Sift-down sai hướng — heapify từ gốc xuống khi build heap ​

❌ Sai lầm 2: Nghĩ build-heap là O(n log n) ​

❌ Sai lầm 3: Mặc định Heap Sort là stable ​

❌ Sai lầm 4: Nhầm index 0-based và 1-based ​

Under the Hood ​

Hiệu năng ​

Tại sao Heap Sort thua Quick Sort trong thực tế ​

So sánh ba thuật toán O(n log n) ​

Trade-offs ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Tìm k phần tử nhỏ nhất — Foundation ​

Bài 2: Heap Sort iterative (không đệ quy) — Intermediate ​

Liên kết học tiếp ​

Heap Sort — Sắp xếp vun đống

Bức tranh tư duy

Cốt lõi kỹ thuật

Binary Heap — cấu trúc nền tảng

Sift-Down (Heapify) — thao tác cốt lõi

Sift-Up vs Sift-Down — hai hướng khác nhau

Build Heap — O(n) chứ không phải O(n log n)

Thuật toán Heap Sort hoàn chỉnh

Thực chiến

Tình huống 1: Priority Queue — hàng đợi ưu tiên

Tình huống 2: Top-K Elements — tìm k phần tử lớn nhất

Tình huống 3: Introsort — Heap Sort làm fallback trong production

Sai lầm điển hình

❌ Sai lầm 1: Sift-down sai hướng — heapify từ gốc xuống khi build heap

❌ Sai lầm 2: Nghĩ build-heap là O(n log n)

❌ Sai lầm 3: Mặc định Heap Sort là stable

❌ Sai lầm 4: Nhầm index 0-based và 1-based

Under the Hood

Hiệu năng

Tại sao Heap Sort thua Quick Sort trong thực tế

So sánh ba thuật toán O(n log n)

Trade-offs

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Tìm k phần tử nhỏ nhất — Foundation

Bài 2: Heap Sort iterative (không đệ quy) — Intermediate

Liên kết học tiếp