您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

堆數據結構與堆排序：Java 代碼演示上浮、下沉、建堆全過程

編輯：Java 相關知識

堆是一種完全二叉樹，通常用數組隱式存儲。其核心性質：任意節點的值 ≤（或 ≥）其子節點值。本文以最小堆為例，通過 Java 代碼演示插入上浮、提取最小值下沉、建堆三大核心操作，並給出堆排序完整實現。

一、堆的數組表示與索引關係

根節點索引 0
左子節點：2*i + 1
右子節點：2*i + 2
父節點：(i-1)/2

完全二叉樹特性保證數組存儲緊湊、無空洞，且支持 O(1) 隨機訪問。

二、核心操作代碼實現

1. 上浮 —— 插入新元素

// 最小堆：新元素放末尾，與父節點比較，小於則交換
public void swim(int k) {
    while (k > 0 && less(pq[(k-1)/2], pq[k])) {
        exch(pq, (k-1)/2, k);
        k = (k-1)/2;
    }
}

// 輔助方法
private boolean less(Comparable a, Comparable b) { return a.compareTo(b) < 0; }
private void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; }

2. 下沉 —— 刪除堆頂/調整堆

// 最小堆：從根節點開始，與較小的子節點交換
private void sink(int k, int N) {
    while (2*k + 1 < N) {  // 存在左子節點
        int j = 2*k + 1;   // 左子節點
        if (j+1 < N && less(pq[j+1], pq[j])) j++;  // 右子節點更小
        if (less(pq[k], pq[j])) break;  // 已滿足堆性質
        exch(pq, k, j);
        k = j;
    }
}

3. 建堆 —— 線性時間 O(n)

// 從最後一個非葉子節點倒序下沉
public Heap(Comparable[] items) {
    pq = items;
    N = items.length;
    for (int k = (N-2)/2; k >= 0; k--) {
        sink(k, N);
    }
}

為什麼 O(n)？ 高度為 h 的節點最多下沉 h 步，節點數約 n/2^{h+1}，總操作數 Σ h·n/2^h = O(n)。

三、堆排序實現

public class HeapSort extends BaseSort {
    private int N;
    
    @Override
    public void sort(Comparable[] a) {
        N = a.length;
        
        // 1. 建立最小堆（若需升序用最大堆，這裡演示最小堆得降序）
        for (int k = (N-2)/2; k >= 0; k--) sink(a, k, N);
        
        // 2. 逐個提取最小值到數組末尾
        while (N > 1) {
            exch(a, 0, --N);  // 堆頂與當前末尾交換
            sink(a, 0, N);    // 新堆頂下沉
        }
    }
    
    private void sink(Comparable[] a, int k, int N) {
        while (2*k + 1 < N) {
            int j = 2*k + 1;
            if (j+1 < N && less(a[j+1], a[j])) j++;
            if (less(a[k], a[j])) break;
            exch(a, k, j);
            k = j;
        }
    }
}