Tip

閱讀本節(jié)前，請確保已學(xué)完“堆“章節(jié)。

「堆排序 heap sort」是一種基于堆數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的高效排序算法。我們可以利用已經(jīng)學(xué)過的“建堆操作”和“元素出堆操作”實(shí)現(xiàn)堆排序。

1. 輸入數(shù)組并建立小頂堆，此時(shí)最小元素位于堆頂。
2. 不斷執(zhí)行出堆操作，依次記錄出堆元素，即可得到從小到大排序的序列。

以上方法雖然可行，但需要借助一個(gè)額外數(shù)組來保存彈出的元素，比較浪費(fèi)空間。在實(shí)際中，我們通常使用一種更加優(yōu)雅的實(shí)現(xiàn)方式。

11.7.1   算法流程

設(shè)數(shù)組的長度為 n ，堆排序的流程如圖 11-12 所示。

1. 輸入數(shù)組并建立大頂堆。完成后，最大元素位于堆頂。
2. 將堆頂元素（第一個(gè)元素）與堆底元素（最后一個(gè)元素）交換。完成交換后，堆的長度減 1 ，已排序元素?cái)?shù)量加 1 。
3. 從堆頂元素開始，從頂?shù)降讏?zhí)行堆化操作（Sift Down）。完成堆化后，堆的性質(zhì)得到修復(fù)。
4. 循環(huán)執(zhí)行第 2. 和 3. 步。循環(huán) n?1 輪后，即可完成數(shù)組排序。

Tip

實(shí)際上，元素出堆操作中也包含第 2. 和 3. 步，只是多了一個(gè)彈出元素的步驟。

圖 11-12   堆排序步驟

在代碼實(shí)現(xiàn)中，我們使用了與堆章節(jié)相同的從頂至底堆化 sift_down() 函數(shù)。值得注意的是，由于堆的長度會(huì)隨著提取最大元素而減小，因此我們需要給 sift_down() 函數(shù)添加一個(gè)長度參數(shù) n ，用于指定堆的當(dāng)前有效長度。

heap_sort.cpp

/* 堆的長度為 n ，從節(jié)點(diǎn) i 開始，從頂至底堆化 */
void siftDown(vector<int> &nums, int n, int i) {
    while (true) {
        // 判斷節(jié)點(diǎn) i, l, r 中值最大的節(jié)點(diǎn)，記為 ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // 若節(jié)點(diǎn) i 最大或索引 l, r 越界，則無須繼續(xù)堆化，跳出
        if (ma == i) {
            break;
        }
        // 交換兩節(jié)點(diǎn)
        swap(nums[i], nums[ma]);
        // 循環(huán)向下堆化
        i = ma;
    }
}

/* 堆排序 */
void heapSort(vector<int> &nums) {
    // 建堆操作：堆化除葉節(jié)點(diǎn)以外的其他所有節(jié)點(diǎn)
    for (int i = nums.size() / 2 - 1; i >= 0; --i) {
        siftDown(nums, nums.size(), i);
    }
    // 從堆中提取最大元素，循環(huán) n-1 輪
    for (int i = nums.size() - 1; i > 0; --i) {
        // 交換根節(jié)點(diǎn)與最右葉節(jié)點(diǎn)（即交換首元素與尾元素）
        swap(nums[0], nums[i]);
        // 以根節(jié)點(diǎn)為起點(diǎn)，從頂至底進(jìn)行堆化
        siftDown(nums, i, 0);
    }
}

11.7.2   算法特性?

• 時(shí)間復(fù)雜度 O(nlogn)、非自適應(yīng)排序：建堆操作使用 O(n) 時(shí)間。從堆中提取最大元素的時(shí)間復(fù)雜度為 O(log?n) ，共循環(huán) n?1 輪。
• 空間復(fù)雜度 O(1)、原地排序：幾個(gè)指針變量使用 O(1) 空間。元素交換和堆化操作都是在原數(shù)組上進(jìn)行的。
• 非穩(wěn)定排序：在交換堆頂元素和堆底元素時(shí)，相等元素的相對位置可能發(fā)生變化。