如何構建最小和最大堆
數據結構在計算機編程中非常重要，可以快速有效地組織、管理和存儲數據。數據結構對于任何開發人員來說都是其工具包中絕對必要的技能。
此篇文章重點關注堆，這是一種特殊的基于樹的數據結構，它實現了完整的二叉樹。
什么是堆？
堆是一種高級的基于樹的數據結構，主要用于排序和實現優先級隊列。它們是完全二叉樹，具有以下特征：
- 除了葉節點（沒有子節點的節點稱為葉節點）之外，每個級別都已填充。
- 每個節點最多有 2 個子節點。
- 所有節點都盡可能遠離左側，這意味著每個子節點都位于其父節點的左側。
堆使用完全二叉樹來避免數組中出現漏洞。完全二叉樹是每個節點最多有兩個子節點的樹，除了葉節點可以為空之外，所有級別的節點都是滿的。堆是根據堆屬性構建的，它將父節點鍵與其子節點鍵進行比較。
在本文的后面部分，我們將詳細討論基于最小堆屬性構建的最小堆和基于最大堆屬性構建的最大堆。
需要注意的是，堆并不總是排序的，它們遵循的關鍵條件是最大或最小元素放置在根節點（頂部）上，具體取決于它是最大堆還是最小堆。堆數據結構與堆內存不同。
堆的優點和缺點
優點：
- 垃圾收集在堆內存上運行以釋放對象使用的內存。
- 堆很靈活，因為可以按任何順序分配或刪除內存。
- 變量可以全局訪問。
- 它有助于找到最小和最大數字。
缺點：
- 與堆棧相比，堆需要更多的執行時間。
- 堆內存中的內存管理更加復雜，因為它是全局使用的。
- 堆通常需要更多時間來計算。
堆數據結構的應用
堆對于查找數組中的最小或最大元素非常有效，并且對于順序統計和選擇算法很有用。從堆中獲取最小值/最大值的時間復雜度為O（1），（恒定時間復雜度）。
優先級隊列是基于堆結構設計的。它需要氧O ( log ( n ) ) 有效地插入（insert()）和刪除（delete()）優先級隊列中每個元素的時間。
堆實現的優先級隊列用于流行的算法，例如：
- 普利姆（Prim’s）算法
- 迪杰斯特拉算法
- 堆排序算法
堆中的基本操作
以下是實現堆數據結構時可能使用的基本操作：
- heapify：重新排列堆中的元素以保持堆屬性。
- insert：將項目添加到堆中，同時保持其堆屬性。
- delete：刪除堆中的項目。
- extract：返回一個項目的值，然后將其從堆中刪除。
- isEmpty： boolean，如果boolean為空則返回true，如果有節點則返回false。
- size：返回堆的大小。
- getMax()：返回堆中的最大值
如何構建最大堆
最大堆中的元素遵循最大堆屬性。這意味著父節點的鍵始終大于兩個子節點的鍵。要構建最大堆：
- 在堆的開頭（根）創建一個新節點。
- 為其指定一個值。
- 將子節點的值與父節點的值進行比較。
- 如果父節點的值小于任一子節點的值（向左或向右），則交換節點。
- 重復此操作，直到最大元素位于根父節點（此時可以說堆屬性成立）。
將新元素插入堆時也可以遵循這些步驟。這里的關鍵是，無論在最大堆上執行什么操作，都必須維護堆屬性。
要移除/刪除最大堆中的根節點：
- 刪除根節點。
- 將最后一層的最后一個子節點移動到根。
- 將父節點與其子節點進行比較。
- 如果父節點的值小于子節點，則交換它們，并重復直到滿足堆屬性。
讓我們看一下代碼中的樣子。我們將使用JavaScript實現最大堆。
在 JavaScript 中實現最大堆
在我們開始構建最大堆之前，先看一下我們將實現的一些方法及其用途：
- _percolateUp()：將堆屬性從子節點恢復到根節點。
- _maxHeapify()：將堆屬性從特定節點恢復到葉節點。
- insert()：將給定值附加到堆數組并根據元素的堆屬性重新排列元素。在每個新插入中，堆均勻增長，并且大小增加一。
- getMax()：返回堆（根節點）中的最大值，不修改堆。注意這里的時間復雜度是常數時間氧（1）歐（1 ）
- removeMax()：返回并刪除堆中的最大值（想想pop()）。該函數的時間復雜度為O ( log ( n ) ) 。
如果堆大小大于一，它將最大值存儲到變量中，將該值與最后一個葉子交換，然后從堆中刪除最大值。
如果堆只有一個元素，則刪除并返回該元素的值，最后一個條件是如果堆為空，則返回 null。
該__percolateUp()方法在每個父節點上遞歸調用，直到到達根。對于要定位在 max-heap 屬性之后的每個節點，我們__maxHeapify()從堆底部開始在該數組的每個索引處調用該方法。
class maxHeap {
constructor() {
this.heap = [];
this.elements = 0;
};
insert(val) {
if (this.elements >= this.heap.length) {
this.elements = this.elements + 1;
this.heap.push(val);
this.__percolateUp(this.heap.length - 1);
}
else {
this.heap[this.elements] = val;
this.elements = this.elements + 1;
this.__percolateUp(this.elements - 1);
}
};
getMax() {
if (this.elements !== 0)
return this.heap[0];
return null;
};
removeMax() {
let max = this.heap[0];
if (this.elements > 1) {
this.heap[0] = this.heap[this.elements - 1];
this.elements = this.elements - 1;
this.__maxHeapify(0);
return max
} else if (this.elements === 1) {
this.elements = this.elements - 1;
return max;
} else {
return null;
}
};
__percolateUp(index) {
const parent = Math.floor((index - 1) / 2);
if (index <= 0)
return
else if (this.heap[parent] < this.heap[index]) {
let tmp = this.heap[parent];
this.heap[parent] = this.heap[index];
this.heap[index] = tmp;
this.__percolateUp(parent);
}
};
__maxHeapify(index) {
let left = (index * 2) + 1;
let right = (index * 2) + 2;
let largest = index;
if ((this.elements > left) && (this.heap[largest] < this.heap[left])) {
largest = left
}
else if ((this.elements > right) && (this.heap[largest] < this.heap[right]))
largest = right
else if (largest !== index) {
const tmp = this.heap[largest];
this.heap[largest] = this.heap[index];
this.heap[index] = tmp;
this.__maxHeapify(largest);
}
};
buildHeap(arr) {
this.heap = arr;
this.elements = this.heap.length;
for (let i = this.heap.length - 1; i >= 0; i--) {
this.__maxHeapify(i);
}
};
};
let heap = new maxHeap();如何構建最小堆
直觀上，我們可以說最小堆中的元素遵循最小堆屬性，因為這與最大堆相反。父節點的鍵始終小于兩個子節點的鍵。為了構建最小堆，我們：
- 在堆的末尾（最后一層）創建一個新的子節點。
- 將新鍵添加到該節點（將其附加到數組）。
- 向上移動子節點，直到到達根節點并且滿足堆屬性。
要移除/刪除最小堆中的根節點：
- 刪除根節點。
- 將最后一個子項的密鑰移至 root。
- 將父節點與其子節點進行比較。
- 如果父節點的值大于子節點，則交換它們，并重復直到滿足堆屬性。
在 JavaScript 中實現最小堆
在我們開始構建最小堆之前，請注意它的實現與最大堆類似。minHeapify()恢復堆屬性。getMin()返回堆（根節點）中的最小值，而不修改堆。并removeMin()刪除最小值并返回它。
class minHeap {
constructor() {
this.heap = []
this.elements = 0;
};
insert(val) {
if (this.elements >== this.heap.length) {
this.elements = this.elements + 1
this.heap.push(val);
this.__percolateUp(this.heap.length - 1);
}
else {
this.heap[this.elements] = val;
this.elements = this.elements + 1;
this.__percolateUp(this.elements - 1);
}
};
getMin() {
if (this.heap.length !== 0)
return this.heap[0];
return null;
}
removeMin() {
const min = this.heap[0];
if (this.elements > 1) {
this.heap[0] = this.heap[this.elements - 1];
this.elements = this.elements - 1;
this.__minHeapify(0);
return min;
} else if (this.elements == 1) {
this.elements = this.elements - 1;
return min;
} else {
return null;
}
};
__percolateUp(index) {
let parent = Math.floor((index - 1) / 2);
if (index <= 0)
return
else if (this.heap[parent] > this.heap[index]) {
let tmp = this.heap[parent];
this.heap[parent] = this.heap[index];
this.heap[index] = tmp;
this.__percolateUp(parent);
}
};
__minHeapify(index) {
let left = (index * 2) + 1;
let right = (index * 2) + 2;
let smallest = index;
if ((this.elements > left) && (this.heap[smallest] > this.heap[left])) {
smallest = left;
}
if ((this.elements > right) && (this.heap[smallest] > this.heap[right]))
smallest = right;
if (smallest !== index) {
let tmp = this.heap[smallest];
this.heap[smallest] = this.heap[index];
this.heap[index] = tmp;
this.__minHeapify(smallest);
}
}
buildHeap(arr) {
this.heap = arr;
this.elements = this.heap.length;
for (let i = this.heap.length - 1; i >= 0; i--) {
this.__minHeapify(i)
}
}
};
let heap = new minHeap();
heap.insert(12);
heap.insert(10);
heap.insert(-10);
heap.insert(100);
console.log(heap.getMin()); //你應該得到-10
let newheap = new minHeap();
let arr = [12, 6, 8, 3, 16, 4, 27];
newheap.buildHeap(arr) //使用數組中的元素構建這個堆
console.log(newheap.getMin()) //這里記錄了 3
newheap.removeMin();
console.log(newheap.getMin())堆進階：將最大堆轉換為最小堆
讓我們通過實踐挑戰使我們的學習更進一步。我們的目標是將最大堆轉換為最小堆。跟隨我們的代碼解決方案看看它是如何完成的。
問題描述：實現一個函數convertMax(maxHeap)，將二進制最大堆轉換為二進制最小堆，其中maxHeap是 格式的數組maxHeap（即父級大于子級）。您的輸出應該是轉換后的數組。
輸入示例：
maxHeap = [9,4,7,1,-2,6,5]示例輸出：
result = [-2,1,5,9,4,6,7]
function convertMax(maxHeap) {
return maxHeap
}上面的代碼解決方案可以運行。我們可以將給定視為maxHeap一個規則的元素數組，并將其重新排序，以便它準確地表示最小堆。該函數通過在每個節點上convertMax()調用該函數，從最低父節點開始恢復所有節點上的堆屬性。minHeapify()
構建堆的時間復雜度為O ( n )。對于這個問題也是如此。
function minHeapify(heap, index) {
var left = index * 2;
var right = (index * 2) + 1;
var smallest = index;
if ((heap.length > left) && (heap[smallest] > heap[left])) {
smallest = left
}
if ((heap.length > right) && (heap[smallest] > heap[right]))
smallest = right
if (smallest != index) {
var tmp = heap[smallest]
heap[smallest] = heap[index]
heap[index] = tmp
minHeapify(heap, smallest)
}
return heap;
}
function convertMax(maxHeap) {
for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
maxHeap = minHeapify(maxHeap, i)
return maxHeap
}
var maxHeap = [9,4,7,1,-2,6,5]
console.log(convertMax(maxHeap))常見的問題
以下是一些常見的挑戰，有助于測試您對堆數據結構的了解。可能會在編碼面試中看到以下問題：
- 將最大堆轉換為最小堆
- 查找數組中 k 個最小元素
- 查找數組中第 k 個最大元素
- 檢查給定數組是否代表最小堆
- 合并M個可變長度的排序列表
- 從每個給定列表中查找至少包含一個元素的最小范圍
嘗試解決這些問題，對堆數據結構會有更深入的了解！
總結
總結來說，構建最小堆和最大堆的步驟都是逐個插入元素，并通過與父節點的比較來調整元素的位置，以滿足堆的性質。這樣可以構建一個高效的數據結構，用于高效地插入、刪除和訪問優先級順序的元素。
