在計算機科學中，堆（Heap）是一種特殊的樹形數據結構，它通常用于實現優先隊列。堆在Java中的應用非常廣泛，尤其是在需要高效處理優先級任務的場景中。本文將詳細介紹堆的基本概念、實現方式、應用場景以及在Java中的具體實現。
堆是一種完全二叉樹，它滿足堆性質：對于最大堆，每個節點的值都大于或等于其子節點的值；對于最小堆，每個節點的值都小于或等于其子節點的值。
堆通常使用數組來存儲，因為完全二叉樹的性質使得數組可以高效地表示堆結構。對于數組中的第i個元素：
- 父節點：(i - 1) / 2
- 左子節點：2 * i + 1
- 右子節點：2 * i + 2
插入操作是將一個新元素添加到堆中，并保持堆的性質。具體步驟如下： 1. 將新元素添加到數組的末尾。 2. 從新元素開始，向上調整堆，直到滿足堆性質。
public void insert(int value) {
heap.add(value);
int current = heap.size() - 1;
while (current > 0 && heap.get(current) > heap.get((current - 1) / 2)) {
swap(current, (current - 1) / 2);
current = (current - 1) / 2;
}
}
刪除操作通常是指刪除堆頂元素，并保持堆的性質。具體步驟如下： 1. 將堆頂元素與數組末尾元素交換。 2. 刪除數組末尾元素。 3. 從堆頂開始，向下調整堆，直到滿足堆性質。
public int delete() {
int max = heap.get(0);
heap.set(0, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
heapify(0);
return max;
}
堆化操作是指將一個不滿足堆性質的子樹調整為滿足堆性質。堆化操作分為向上堆化和向下堆化。
public void heapify(int i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < heap.size() && heap.get(left) > heap.get(largest)) {
largest = left;
}
if (right < heap.size() && heap.get(right) > heap.get(largest)) {
largest = right;
}
if (largest != i) {
swap(i, largest);
heapify(largest);
}
}
優先隊列是一種特殊的隊列，其中每個元素都有一個優先級，優先級最高的元素最先出隊。堆是實現優先隊列的理想數據結構。
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(30);
pq.add(20);
System.out.println(pq.poll()); // 輸出10
堆排序是一種基于堆的排序算法，其時間復雜度為O(n log n)。堆排序的基本思想是將待排序的序列構造成一個最大堆，然后依次將堆頂元素與末尾元素交換，并調整堆。
public 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);
}
}
Top K問題是指從一組數據中找出前K個最大或最小的元素。堆可以高效地解決Top K問題。
public int[] topK(int[] arr, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : arr) {
pq.add(num);
if (pq.size() > k) {
pq.poll();
}
}
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = pq.poll();
}
return result;
}
Dijkstra算法是一種用于計算單源最短路徑的算法。在Dijkstra算法中，堆用于高效地選擇當前最短路徑的節點。
public void dijkstra(int[][] graph, int src) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.add(new int[]{src, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int u = current[0];
for (int v = 0; v < n; v++) {
if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
pq.add(new int[]{v, dist[v]});
}
}
}
}
Java中的PriorityQueue類是基于堆實現的優先隊列。它提供了插入、刪除、查看堆頂元素等操作。
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(30);
pq.add(20);
System.out.println(pq.poll()); // 輸出10
除了使用PriorityQueue，我們還可以自定義堆的實現。以下是一個簡單的最大堆實現：
public class MaxHeap {
private List<Integer> heap;
public MaxHeap() {
heap = new ArrayList<>();
}
public void insert(int value) {
heap.add(value);
int current = heap.size() - 1;
while (current > 0 && heap.get(current) > heap.get((current - 1) / 2)) {
swap(current, (current - 1) / 2);
current = (current - 1) / 2;
}
}
public int delete() {
int max = heap.get(0);
heap.set(0, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
heapify(0);
return max;
}
private void heapify(int i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < heap.size() && heap.get(left) > heap.get(largest)) {
largest = left;
}
if (right < heap.size() && heap.get(right) > heap.get(largest)) {
largest = right;
}
if (largest != i) {
swap(i, largest);
heapify(largest);
}
}
private void swap(int i, int j) {
int temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
}
斐波那契堆是一種更高效的堆結構，它在某些操作（如合并堆）上具有更好的時間復雜度。斐波那契堆的插入、刪除、合并等操作的時間復雜度為O(1)。
二項堆是由多個二項樹組成的堆結構，它在合并操作上具有較好的性能。二項堆的插入、刪除、合并等操作的時間復雜度為O(log n)。
堆是一種非常重要的數據結構，它在Java中的應用非常廣泛。通過本文的介紹，我們了解了堆的基本概念、實現方式、應用場景以及在Java中的具體實現。堆在優先隊列、堆排序、Top K問題、Dijkstra算法等場景中發揮著重要作用。希望本文能幫助讀者更好地理解和應用堆這一數據結構。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
