算法入門排序算法：堆排序

一、什么是堆排序？

堆排序（Heap Sort）是一種基于二叉堆數(shù)據(jù)結(jié)構(gòu)的高效排序算法，由J. W. J. Williams于1964年發(fā)明。它結(jié)合了插入排序和歸并排序的優(yōu)點(diǎn)：像插入排序一樣是原地排序，像歸并排序一樣具有O(n log n)的時(shí)間復(fù)雜度。

堆排序的核心數(shù)據(jù)結(jié)構(gòu)是堆——一種特殊的完全二叉樹，它滿足堆屬性：每個(gè)節(jié)點(diǎn)的值都大于或等于（最大堆）或小于或等于（最小堆）其子節(jié)點(diǎn)的值。

二、堆排序的工作原理

堆排序的過程可以分為兩個(gè)主要階段：

構(gòu)建堆（Heapify）：將無(wú)序數(shù)組構(gòu)建成一個(gè)最大堆（或最小堆）
排序：反復(fù)將堆頂元素（最大或最小元素）與堆末尾元素交換，然后重新調(diào)整堆

這個(gè)過程就像是在篩選石子：先把所有石子堆成一個(gè)大堆（最大的石頭在頂部），然后每次取走頂部的最大石頭，重新調(diào)整堆，直到所有石頭都按順序取完。

三、堆排序的Java實(shí)現(xiàn)

下面是堆排序的完整Java實(shí)現(xiàn)，包含詳細(xì)注釋：

import java.util.Arrays;

public class HeapSort {

    // 堆排序主方法
    public static void heapSort(int[] array) {
        int n = array.length;

        System.out.println("原始數(shù)組: " + Arrays.toString(array));

        // 1. 構(gòu)建最大堆
        System.out.println("開始構(gòu)建最大堆...");
        buildMaxHeap(array);
        System.out.println("最大堆構(gòu)建完成: " + Arrays.toString(array));

        // 2. 逐個(gè)提取元素
        System.out.println("開始排序過程...");
        for (int i = n - 1; i > 0; i--) {
            // 將當(dāng)前堆頂（最大值）與末尾元素交換
            swap(array, 0, i);
            System.out.println("交換堆頂與位置" + i + "后: " + Arrays.toString(array));

            // 調(diào)整剩余元素，使其保持堆屬性
            maxHeapify(array, i, 0);
            System.out.println("調(diào)整堆后: " + Arrays.toString(array));
        }
    }

    // 構(gòu)建最大堆
    private static void buildMaxHeap(int[] array) {
        int n = array.length;

        // 從最后一個(gè)非葉子節(jié)點(diǎn)開始，向上調(diào)整
        // 最后一個(gè)非葉子節(jié)點(diǎn)的索引 = (n/2) - 1
        for (int i = n / 2 - 1; i >= 0; i--) {
            maxHeapify(array, n, i);
        }
    }

    // 調(diào)整堆，使其滿足最大堆屬性
    private static void maxHeapify(int[] array, int heapSize, int rootIndex) {
        int largest = rootIndex;      // 假設(shè)根節(jié)點(diǎn)是最大的
        int leftChild = 2 * rootIndex + 1;   // 左子節(jié)點(diǎn)索引
        int rightChild = 2 * rootIndex + 2;  // 右子節(jié)點(diǎn)索引

        // 如果左子節(jié)點(diǎn)存在且大于根節(jié)點(diǎn)
        if (leftChild < heapSize && array[leftChild] > array[largest]) {
            largest = leftChild;
        }

        // 如果右子節(jié)點(diǎn)存在且大于當(dāng)前最大值
        if (rightChild < heapSize && array[rightChild] > array[largest]) {
            largest = rightChild;
        }

        // 如果最大值不是根節(jié)點(diǎn)，需要交換并繼續(xù)調(diào)整
        if (largest != rootIndex) {
            swap(array, rootIndex, largest);
            // 遞歸調(diào)整受影響的子樹
            maxHeapify(array, heapSize, largest);
        }
    }

    // 交換數(shù)組中的兩個(gè)元素
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // 可視化堆結(jié)構(gòu)（輔助理解）
    public static void printHeap(int[] array, int heapSize) {
        System.out.println("堆結(jié)構(gòu)可視化:");
        int levels = (int) (Math.log(heapSize) / Math.log(2)) + 1;
        int currentIndex = 0;

        for (int level = 0; level < levels; level++) {
            int elementsInLevel = (int) Math.pow(2, level);
            int padding = (int) Math.pow(2, levels - level) - 1;

            // 打印前導(dǎo)空格
            for (int i = 0; i < padding; i++) {
                System.out.print(" ");
            }

            // 打印當(dāng)前層的元素
            for (int i = 0; i < elementsInLevel && currentIndex < heapSize; i++) {
                System.out.print(array[currentIndex++]);
                for (int j = 0; j < padding * 2 + 1; j++) {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[] data = {4, 10, 3, 5, 1, 8, 7, 2, 9, 6};

        System.out.println("=== 堆排序演示 ===");
        heapSort(data);

        System.out.println("最終排序結(jié)果: " + Arrays.toString(data));

        // 額外演示：最小堆排序
        System.out.println("\n=== 最小堆排序演示 ===");
        int[] data2 = {4, 10, 3, 5, 1, 8, 7, 2, 9, 6};
        heapSortMin(data2);
        System.out.println("最小堆排序結(jié)果: " + Arrays.toString(data2));
    }

    // 最小堆排序版本
    public static void heapSortMin(int[] array) {
        int n = array.length;

        // 構(gòu)建最小堆
        buildMinHeap(array);

        // 逐個(gè)提取元素
        for (int i = n - 1; i > 0; i--) {
            swap(array, 0, i);
            minHeapify(array, i, 0);
        }
    }

    // 構(gòu)建最小堆
    private static void buildMinHeap(int[] array) {
        int n = array.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            minHeapify(array, n, i);
        }
    }

    // 調(diào)整最小堆
    private static void minHeapify(int[] array, int heapSize, int rootIndex) {
        int smallest = rootIndex;
        int leftChild = 2 * rootIndex + 1;
        int rightChild = 2 * rootIndex + 2;

        if (leftChild < heapSize && array[leftChild] < array[smallest]) {
            smallest = leftChild;
        }

        if (rightChild < heapSize && array[rightChild] < array[smallest]) {
            smallest = rightChild;
        }

        if (smallest != rootIndex) {
            swap(array, rootIndex, smallest);
            minHeapify(array, heapSize, smallest);
        }
    }
}

代碼解析：

堆構(gòu)建：
- buildMaxHeap()：從最后一個(gè)非葉子節(jié)點(diǎn)開始，自底向上構(gòu)建最大堆
- maxHeapify()：調(diào)整指定節(jié)點(diǎn)及其子樹，使其滿足堆屬性
排序過程：
- 將堆頂元素（最大值）與末尾元素交換
- 堆大小減1，重新調(diào)整堆
- 重復(fù)直到堆中只剩一個(gè)元素
輔助方法：
- swap()：交換數(shù)組元素
- printHeap()：可視化堆結(jié)構(gòu)，幫助理解
- 最小堆版本：演示降序排序

四、堆排序的性能分析

時(shí)間復(fù)雜度：

構(gòu)建堆：O(n) —— 看似是O(n log n)，但通過數(shù)學(xué)分析可知是O(n)
每次調(diào)整堆：O(log n)
總時(shí)間復(fù)雜度：O(n log n)

空間復(fù)雜度：

堆排序是原地排序算法，只需要常數(shù)級(jí)別的額外空間（O(1)），用于臨時(shí)存儲(chǔ)交換的變量。

穩(wěn)定性：

堆排序是不穩(wěn)定的排序算法，因?yàn)槎颜{(diào)整過程中的交換可能改變相等元素的相對(duì)順序。

五、堆排序的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

時(shí)間復(fù)雜度穩(wěn)定為O(n log n)，沒有最壞情況
原地排序，空間效率高
適用于大規(guī)模數(shù)據(jù)排序
可以高效實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列

缺點(diǎn)：

不穩(wěn)定排序
緩存不友好（跳躍式訪問模式）
常數(shù)因子較大，實(shí)際運(yùn)行可能不如快速排序快
實(shí)現(xiàn)相對(duì)復(fù)雜

六、堆排序的實(shí)際應(yīng)用

堆排序在以下場(chǎng)景中特別有用：

優(yōu)先級(jí)隊(duì)列：堆是優(yōu)先級(jí)隊(duì)列的理想數(shù)據(jù)結(jié)構(gòu)
實(shí)時(shí)系統(tǒng)：需要保證最壞情況下性能的場(chǎng)景
外部排序：處理無(wú)法全部裝入內(nèi)存的大數(shù)據(jù)集
游戲開發(fā)：需要高效處理動(dòng)態(tài)優(yōu)先級(jí)的情況
操作系統(tǒng)：進(jìn)程調(diào)度、內(nèi)存管理等

七、堆排序的變體和優(yōu)化

二叉堆：最基礎(chǔ)的堆實(shí)現(xiàn)，使用數(shù)組存儲(chǔ)
二項(xiàng)堆：支持高效合并操作的堆變體
斐波那契堆：理論上最優(yōu)的堆結(jié)構(gòu)，但實(shí)現(xiàn)復(fù)雜
d-堆：每個(gè)節(jié)點(diǎn)有d個(gè)子節(jié)點(diǎn)，適合外部存儲(chǔ)
左傾堆：支持高效合并的另一種堆結(jié)構(gòu)

八、堆的數(shù)學(xué)性質(zhì)

堆作為完全二叉樹，具有以下重要性質(zhì)：

高度：?log?n?
非葉子節(jié)點(diǎn)范圍：0 到 ?n/2? - 1
節(jié)點(diǎn)i的子節(jié)點(diǎn)：2i+1 和 2i+2
節(jié)點(diǎn)i的父節(jié)點(diǎn)：?(i-1)/2?

這些性質(zhì)使得我們可以用數(shù)組高效地表示堆，而不需要顯式的指針結(jié)構(gòu)。

九、總結(jié)

堆排序以其穩(wěn)定的O(n log n)時(shí)間復(fù)雜度和原地排序的特性，在算法世界中占有重要地位。雖然在實(shí)際應(yīng)用中可能不如快速排序快，但它的最壞情況保證使其在需要可靠性的場(chǎng)景中不可替代。

理解堆排序不僅有助于掌握一種高效的排序算法，還能深入理解堆這一重要數(shù)據(jù)結(jié)構(gòu)。堆作為優(yōu)先級(jí)隊(duì)列的基礎(chǔ)，在操作系統(tǒng)、數(shù)據(jù)庫(kù)、網(wǎng)絡(luò)調(diào)度等眾多領(lǐng)域都有廣泛應(yīng)用。

正如計(jì)算機(jī)科學(xué)家Robert Sedgewick所說(shuō)："堆排序是唯一能夠同時(shí)保證O(n log n)時(shí)間和O(1)空間的比較排序算法。"這種獨(dú)特的性能特征使堆排序在理論研究和實(shí)際應(yīng)用中都具有重要價(jià)值。

掌握堆排序，意味著你不僅學(xué)會(huì)了一種排序算法，更理解了一種重要的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和分析方法。這是每個(gè)計(jì)算機(jī)科學(xué)學(xué)習(xí)者的必修課。

posted @ 2025-08-27 10:41 高級(jí)摸魚工程師閱讀(76) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

famous-oneday