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