STL 堆算法核心實現深度解析與對比驗證

背景

本文以純 C 風格重新實現 STL `` 中四大堆操作：push_heap、pop_heap、make_heap、sort_heap，並對照標準庫行為驗證正確性。去除 C++ 樣板與迭代器抽象，聚焦算法邏輯本質。

核心數據結構：最大堆（Max-Heap）

• 陣列隱式完全二叉樹：父節點 i，左子 2i+1，右子 2i+2，父節點 (i-1)/2。
• 堆性質：任一節點 ≥ 其子節點值（根節點為最大值）。

四大操作實現詳解

1. push_heap：插入新元素（上浮）

void push_heap(int* pFirst, int* pLast) {
    int nTopIndex = 0;
    int nHoleIndex = (pLast - pFirst) - 1;  // 新元素索引
    int nParentIndex = (nHoleIndex - 1) / 2;
    int nValue = *(pLast - 1);              // 新元素值

    while (nHoleIndex > nTopIndex && pFirst[nParentIndex] < nValue) {
        pFirst[nHoleIndex] = pFirst[nParentIndex];  // 父節點下沉
        nHoleIndex = nParentIndex;
        nParentIndex = (nHoleIndex - 1) / 2;
    }
    pFirst[nHoleIndex] = nValue;  // 空洞處填入新值
}

前提：[First, Last-1) 已滿足堆性質。複雜度：O(log n)。

2. pop_heap：移除堆頂（下沉）

void pop_heap(int* pFirst, int* pLast) {
    int nValue = *(pLast - 1);           // 保存末尾元素
    *(pLast - 1) = *pFirst;              // 堆頂移至末尾（輸出最大值）
    adjust_heap(pFirst, 0, (pLast - pFirst) - 1, nValue);  // 從根重建堆
}

效果：最大值移至 Last-1，[First, Last-1) 重建為堆。複雜度：O(log n)。

3. make_heap：建堆（自底向下）

void make_heap(int* pFirst, int* pLast) {
    int nLen = pLast - pFirst;
    int nParentIndex = (nLen - 1) / 2;  // 最後一個非葉節點
    while (true) {
        adjust_heap(pFirst, nParentIndex, nLen, pFirst[nParentIndex]);
        if (nParentIndex == 0) return;
        nParentIndex--;
    }
}

原理：從最後非葉節點遞迴向根調用 adjust_heap，保證子樹先成堆。複雜度：O(n)。

4. sort_heap：堆排序（反覆 pop_heap）

void sort_heap(int* pFirst, int* pLast) {
    while (pLast - pFirst > 1)
        pop_heap(pFirst, pLast--);  // 逐個取出最大值至序列末尾
}

前提：輸入範圍已為堆。複雜度：O(n log n)，原地排序，不穩定。

核心輔助函數：adjust_heap（下沉重建）

static void adjust_heap(int* pFirst, int nHoleIndex, int nLen, int nValue) {
    int nTopIndex = nHoleIndex;
    int nSecondChildIndex = 2 * nTopIndex + 2;  // 右子節點

    // 向下找到較大子節點，將其上移填補空洞
    while (nSecondChildIndex < nLen) {
        if (pFirst[nSecondChildIndex] < pFirst[nSecondChildIndex - 1])
            --nSecondChildIndex;  // 左子較大
        pFirst[nHoleIndex] = pFirst[nSecondChildIndex];
        nHoleIndex = nSecondChildIndex;
        nSecondChildIndex = 2 * nHoleIndex + 2;
    }

    // 處理僅有左子節點的情況
    if (nSecondChildIndex == nLen) {
        pFirst[nHoleIndex] = pFirst[nSecondChildIndex - 1];
        nHoleIndex = nSecondChildIndex - 1;
    }

    // 將保存的值上浮至合適位置（等價於 push_heap 邏輯）
    push_heap(pFirst, nHoleIndex, nTopIndex, nValue);
}

驗證工具：is_heap

char is_heap(int* pFirst, int* pLast) {
    int nLen = pLast - pFirst, nParentIndex = 0;
    for (int nChildIndex = 1; nChildIndex < nLen; ++nChildIndex) {
        if (pFirst[nParentIndex] < pFirst[nChildIndex]) return 0;
        if ((nChildIndex & 1) == 0) ++nParentIndex;  // 偶數索引→父節點遞增
    }
    return 1;
}

對比測試框架

void test_heap_algo(int* pArray, int nLength) {
    make_heap(pArray, pArray + nLength);  display(pArray, nLength);
    push_heap(pArray, pArray + nLength);  display(pArray, nLength);
    pop_heap(pArray, pArray + nLength);   display(pArray, nLength);
    assert(is_heap(pArray, pArray + nLength - 1));
    make_heap(pArray, pArray + nLength);  display(pArray, nLength);
    assert(is_heap(pArray, pArray + nLength));
    sort_heap(pArray, pArray + nLength);  display(pArray, nLength);
}

void test_heap_algo_in_stl(int* pArray, int nLength) {
    std::make_heap(pArray, pArray + nLength);  display(pArray, nLength);
    std::push_heap(pArray, pArray + nLength);  display(pArray, nLength);
    std::pop_heap(pArray, pArray + nLength);   display(pArray, nLength);
    assert(is_heap(pArray, pArray + nLength - 1));
    std::make_heap(pArray, pArray + nLength);  display(pArray, nLength);
    assert(is_heap(pArray, pArray + nLength));
    std::sort_heap(pArray, pArray + nLength);  display(pArray, nLength);
}

關鍵洞見

• adjust_heap 結尾以 push_heap 完成上浮，證明「下沉找位 + 上浮填值」等價於單次完整下沉（STL 來源碼剖析 P178 JJHOU 結論）。
• 純指標運算版本與 STL 樣板版本行為完全一致，驗證算法正確性。
• is_heap 非標準算法（SGI STL 擴展），但極實用於除錯。