鴻蒙OS 4.0公測(cè)機(jī)型公布：甚至連nova6都支持
華為全新的HarmonyOS 4.0操作系統(tǒng)將于今天下午正式登場(chǎng)，官方在發(fā)布會(huì)之前也已經(jīng)正式給出了可升級(jí)的機(jī)型產(chǎn)品，這意味著這些機(jī)型會(huì)率先支持升級(jí)享用。這次的HarmonyOS 4.0支持
數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)編程中非常重要，可以快速有效地組織、管理和存儲(chǔ)數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)對(duì)于任何開發(fā)人員來(lái)說(shuō)都是其工具包中絕對(duì)必要的技能。
此篇文章重點(diǎn)關(guān)注堆，這是一種特殊的基于樹的數(shù)據(jù)結(jié)構(gòu)，它實(shí)現(xiàn)了完整的二叉樹。
堆使用完全二叉樹來(lái)避免數(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)：
堆對(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ì)列用于流行的算法，例如：
以下是實(shí)現(xiàn)堆數(shù)據(jù)結(jié)構(gòu)時(shí)可能使用的基本操作：
最大堆中的元素遵循最大堆屬性。這意味著父節(jié)點(diǎn)的鍵始終大于兩個(gè)子節(jié)點(diǎn)的鍵。要構(gòu)建最大堆：
將新元素插入堆時(shí)也可以遵循這些步驟。這里的關(guān)鍵是，無(wú)論在最大堆上執(zhí)行什么操作，都必須維護(hù)堆屬性。
要移除/刪除最大堆中的根節(jié)點(diǎn)：
讓我們看一下代碼中的樣子。我們將使用JavaScript實(shí)現(xiàn)最大堆。
在我們開始構(gòu)建最大堆之前，先看一下我們將實(shí)現(xià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();直觀上，我們可以說(shuō)最小堆中的元素遵循最小堆屬性，因?yàn)檫@與最大堆相反。父節(jié)點(diǎn)的鍵始終小于兩個(gè)子節(jié)點(diǎn)的鍵。為了構(gòu)建最小堆，我們：
要移除/刪除最小堆中的根節(jié)點(diǎ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)該得到-10let newheap = new minHeap();let arr = [12, 6, 8, 3, 16, 4, 27];newheap.buildHeap(arr) //使用數(shù)組中的元素構(gòu)建這個(gè)堆console.log(newheap.getMin()) //這里記錄了 3newheap.removeMin();console.log(newheap.getMin())讓我們通過(guò)實(shí)踐挑戰(zhàn)使我們的學(xué)習(xí)更進(jìn)一步。我們的目標(biāo)是將最大堆轉(zhuǎn)換為最小堆。跟隨我們的代碼解決方案看看它是如何完成的。
問(wè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ù)通過(guò)在每個(gè)節(jié)點(diǎn)上convertMax()調(diào)用該函數(shù)，從最低父節(jié)點(diǎn)開始恢復(fù)所有節(jié)點(diǎn)上的堆屬性。minHeapify()
構(gòu)建堆的時(shí)間復(fù)雜度為O ( n )。對(duì)于這個(gè)問(wè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))以下是一些常見的挑戰(zhàn)，有助于測(cè)試您對(duì)堆數(shù)據(jù)結(jié)構(gòu)的了解。可能會(huì)在編碼面試中看到以下問(wèn)題：
嘗試解決這些問(wèn)題，對(duì)堆數(shù)據(jù)結(jié)構(gòu)會(huì)有更深入的了解！
總結(jié)來(lái)說(shuō)，構(gòu)建最小堆和最大堆的步驟都是逐個(gè)插入元素，并通過(guò)與父節(jié)點(diǎn)的比較來(lái)調(diào)整元素的位置，以滿足堆的性質(zhì)。這樣可以構(gòu)建一個(gè)高效的數(shù)據(jù)結(jié)構(gòu)，用于高效地插入、刪除和訪問(wèn)優(yōu)先級(jí)順序的元素。
本文鏈接：http://www.tebozhan.com/showinfo-26-22482-0.html如何構(gòu)建最小和最大堆
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
上一篇： 又一個(gè)小而美的涵蓋多個(gè)實(shí)際場(chǎng)景的高并發(fā)項(xiàng)目完結(jié)了
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)