?

一、堆的核心概念體系

1. 堆的定義與性質

graph TBROOT((最大堆)) --> A[父節點 ≥ 子節點]ROOT --> B[完全二叉樹結構]ROOT --> C[數組存儲]ROOT --> D[快速獲取極值]

2. 堆類型對比

類型	特性	典型應用場景
最大堆	父節點值 ≥ 子節點值	獲取前K大元素
最小堆	父節點值 ≤ 子節點值	獲取前K小元素
斐波那契堆	平攤O(1)時間復雜度的操作	圖算法優化

---

二、堆的存儲與操作原理

1. 數組存儲結構

索引計算規則（下標從0開始）：

• 父節點：(i-1)/2

• 左子節點：2i+1

• 右子節點：2i+2

示例數組：
[9, 7, 5, 6, 3, 1, 4]
對應堆結構：

       9/   \7     5/ \   / \6   3 1   4

2. 核心操作時間復雜度

操作	時間復雜度	說明
插入元素	O(log n)	上浮(swim)操作
刪除堆頂	O(log n)	下沉(sink)操作
獲取極值	O(1)	直接訪問根節點
構建堆	O(n)	Floyd算法自底向上構建

---

三、Java標準庫實現：PriorityQueue

1. 使用示例

// 最小堆（默認）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();// 最大堆（使用反向比較器）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);// 自定義對象堆
PriorityQueue<Student> stuHeap = new PriorityQueue<>(Comparator.comparingInt(Student::getScore)
);

2. 源碼關鍵實現

// 底層數組存儲
transient Object[] queue;// 上浮操作（插入時）
private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);
}// 下沉操作（刪除時）
private void siftDown(int k, E x) {if (comparator != null)siftDownUsingComparator(k, x);elsesiftDownComparable(k, x);
}

---

四、手動實現堆結構

1. 最小堆完整實現

public class MinHeap {private int[] heap;private int size;private static final int DEFAULT_CAPACITY = 10;public MinHeap() {this(DEFAULT_CAPACITY);}public MinHeap(int capacity) {heap = new int[capacity];}// 插入操作public void insert(int value) {if (size == heap.length) resize();heap[size] = value;swim(size);size++;}// 刪除堆頂public int extractMin() {if (size == 0) throw new IllegalStateException();int min = heap[0];heap[0] = heap[size-1];size--;sink(0);return min;}// 上浮操作private void swim(int k) {while (k > 0 && heap[k] < heap[(k-1)/2]) {swap(k, (k-1)/2);k = (k-1)/2;}}// 下沉操作private void sink(int k) {while (2*k+1 < size) {int j = 2*k+1;if (j+1 < size && heap[j+1] < heap[j]) j++;if (heap[k] <= heap[j]) break;swap(k, j);k = j;}}// 擴容機制private void resize() {heap = Arrays.copyOf(heap, heap.length * 2);}
}

---

五、堆排序算法實現

1. 排序步驟

public static void heapSort(int[] arr) {// 構建最大堆int n = arr.length;for (int i = n/2-1; i >= 0; i--) {heapify(arr, n, i);}// 逐個提取元素for (int i = n-1; i > 0; i--) {swap(arr, 0, i);heapify(arr, i, 0);}
}private static void heapify(int[] arr, int n, int i) {int largest = i;int l = 2*i+1;int r = 2*i+2;if (l < n && arr[l] > arr[largest]) largest = l;if (r < n && arr[r] > arr[largest]) largest = r;if (largest != i) {swap(arr, i, largest);heapify(arr, n, largest);}
}

2. 性能特點

• 時間復雜度：O(n log n)

• 空間復雜度：O(1)（原地排序）

• 不穩定排序算法

---

六、堆的實際應用場景

1. Top K問題

求前K大元素：

public List<Integer> topKElements(int[] nums, int k) {PriorityQueue<Integer> minHeap = new PriorityQueue<>();for (int num : nums) {minHeap.offer(num);if (minHeap.size() > k) {minHeap.poll();}}return new ArrayList<>(minHeap);
}

2. 合并K個有序鏈表

public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));for (ListNode node : lists) {if (node != null) heap.offer(node);}ListNode dummy = new ListNode(0);ListNode curr = dummy;while (!heap.isEmpty()) {ListNode min = heap.poll();curr.next = min;curr = curr.next;if (min.next != null) {heap.offer(min.next);}}return dummy.next;
}

---

七、高級應用與優化

1. 動態數據流的中位數

class MedianFinder {PriorityQueue<Integer> minHeap; // 存儲較大的一半PriorityQueue<Integer> maxHeap; // 存儲較小的一半public MedianFinder() {minHeap = new PriorityQueue<>();maxHeap = new PriorityQueue<>(Collections.reverseOrder());}public void addNum(int num) {maxHeap.offer(num);minHeap.offer(maxHeap.poll());if (maxHeap.size() < minHeap.size()) {maxHeap.offer(minHeap.poll());}}public double findMedian() {return maxHeap.size() > minHeap.size() ? maxHeap.peek() : (maxHeap.peek() + minHeap.peek()) / 2.0;}
}

2. 定時任務調度

class Scheduler {private PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingLong(Task::getExecuteTime));public void addTask(Task task) {taskQueue.offer(task);}public void run() {while (!taskQueue.isEmpty()) {Task task = taskQueue.poll();long current = System.currentTimeMillis();if (task.getExecuteTime() > current) {try {Thread.sleep(task.getExecuteTime() - current);} catch (InterruptedException e) {Thread.currentThread().interrupt();}}task.execute();}}
}

---

八、常見問題與解決方案

1. 如何選擇堆的類型？

場景	推薦堆類型
需要快速獲取最大值	最大堆
高頻插入與刪除最小值	最小堆
數據動態變化的中位數計算	雙堆組合

2. 線程安全問題處理方案

// 使用并發堆實現
PriorityBlockingQueue<Integer> safeHeap = new PriorityBlockingQueue<>();// 手動同步
PriorityQueue<Integer> heap = new PriorityQueue<>();
synchronized(heap) {heap.offer(123);// 其他操作
}

---

九、性能調優技巧

1. 堆初始化優化

// 預估數據量大小，避免頻繁擴容
int expectedSize = 100000;
PriorityQueue<Integer> heap = new PriorityQueue<>(expectedSize);

2. 對象池技術減少GC壓力

class ObjectPool {private PriorityQueue<ReusableObject> pool = new PriorityQueue<>(Comparator.comparingInt(o -> o.priority));public ReusableObject getObject() {return pool.poll() ?? createNewObject();}public void returnObject(ReusableObject obj) {obj.resetState();pool.offer(obj);}
}

---

十、總結與選型建議

堆的核心優勢

• 極值訪問高效：O(1)時間復雜度獲取最大/最小值

• 動態數據管理：持續插入/刪除操作保持高效

• 內存緊湊：數組存儲相比鏈表更節省空間

使用注意事項

• 不支持快速查找：任意元素查找需要O(n)

• 非線程安全：多線程環境需使用并發版本

• 比較器陷阱：自定義比較器需確保邏輯正確

選型決策樹：

需要管理動態數據集？
├── 是 → 需要頻繁獲取極值？
│       ├── 是 → 使用堆結構
│       └── 否 → 考慮哈希表或平衡樹
└── 否 → 使用普通數組

擴展方向：

• 研究斐波那契堆等高級堆結構

• 探索堆在機器學習中的應用（如優先級經驗回放）

• 結合堆外內存實現超大堆結構

通過對堆結構的深入理解和合理應用，開發者可以顯著提升系統在處理優先級任務、實時數據流分析等場景下的性能表現。

?