一文看懂為蘋果Vision Pro開發應用程序
譯者 | 布加迪審校 | 重樓蘋果的Vision Pro是一款混合現實（MR）頭戴設備。Vision Pro結合了虛擬現實（VR）和增強現實（AR）的沉浸感。其高分辨率顯示屏、先進的傳感器和強大的處理能力
數據結構在計算機編程中非常重要，可以快速有效地組織、管理和存儲數據。數據結構對于任何開發人員來說都是其工具包中絕對必要的技能。
此篇文章重點關注堆，這是一種特殊的基于樹的數據結構，它實現了完整的二叉樹。
堆使用完全二叉樹來避免數組中出現漏洞。完全二叉樹是每個節點最多有兩個子節點的樹，除了葉節點可以為空之外，所有級別的節點都是滿的。堆是根據堆屬性構建的，它將父節點鍵與其子節點鍵進行比較。
在本文的后面部分，我們將詳細討論基于最小堆屬性構建的最小堆和基于最大堆屬性構建的最大堆。
需要注意的是，堆并不總是排序的，它們遵循的關鍵條件是最大或最小元素放置在根節點（頂部）上，具體取決于它是最大堆還是最小堆。堆數據結構與堆內存不同。
優點：
缺點：
堆對于查找數組中的最小或最大元素非常有效，并且對于順序統計和選擇算法很有用。從堆中獲取最小值/最大值的時間復雜度為O（1），（恒定時間復雜度）。
優先級隊列是基于堆結構設計的。它需要氧O ( log ( n ) ) 有效地插入（insert()）和刪除（delete()）優先級隊列中每個元素的時間。
堆實現的優先級隊列用于流行的算法，例如：
以下是實現堆數據結構時可能使用的基本操作：
最大堆中的元素遵循最大堆屬性。這意味著父節點的鍵始終大于兩個子節點的鍵。要構建最大堆：
將新元素插入堆時也可以遵循這些步驟。這里的關鍵是，無論在最大堆上執行什么操作，都必須維護堆屬性。
要移除/刪除最大堆中的根節點：
讓我們看一下代碼中的樣子。我們將使用JavaScript實現最大堆。
在我們開始構建最大堆之前，先看一下我們將實現的一些方法及其用途：
如果堆大小大于一，它將最大值存儲到變量中，將該值與最后一個葉子交換，然后從堆中刪除最大值。
如果堆只有一個元素，則刪除并返回該元素的值，最后一個條件是如果堆為空，則返回 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();直觀上，我們可以說最小堆中的元素遵循最小堆屬性，因為這與最大堆相反。父節點的鍵始終小于兩個子節點的鍵。為了構建最小堆，我們：
要移除/刪除最小堆中的根節點：
在我們開始構建最小堆之前，請注意它的實現與最大堆類似。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()); //你應該得到-10let newheap = new minHeap();let arr = [12, 6, 8, 3, 16, 4, 27];newheap.buildHeap(arr) //使用數組中的元素構建這個堆console.log(newheap.getMin()) //這里記錄了 3newheap.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))以下是一些常見的挑戰，有助于測試您對堆數據結構的了解。可能會在編碼面試中看到以下問題：
嘗試解決這些問題，對堆數據結構會有更深入的了解！
總結來說，構建最小堆和最大堆的步驟都是逐個插入元素，并通過與父節點的比較來調整元素的位置，以滿足堆的性質。這樣可以構建一個高效的數據結構，用于高效地插入、刪除和訪問優先級順序的元素。
本文鏈接：http://www.www897cc.com/showinfo-26-22482-0.html如何構建最小和最大堆
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號