什么是堆？
堆是一种高级的基于树的数据结构， 主要用于排序和实现优先级[队列]它们是具有以下特征的完全二叉树：
- 除了叶节点（没有子节点的节点称为叶）之外，每个级别都被填充。
- 每个节点最多有 2 个孩子。
- 所有节点都尽可能靠左。这意味着每个孩子都在他父母的左边。
网络异常，图片无法展示
|
堆使用完全二叉树来避免数组中出现空洞。完全二叉树是每个结点至多有两个孩子的树，所有层的结点都是满的，除了叶子结点可以为空。堆是基于堆属性构建的，堆属性将父节点键与其子节点键进行比较。
重要的是要注意堆并不总是排序的。它们遵循的关键条件是最大或最小元素放置在根节点（顶部）上，具体取决于它是最大堆还是最小堆。堆数据结构与堆内存不同。
堆的优点和缺点
优点：
- 垃圾收集在堆内存上运行以释放对象使用的内存。
- 堆是灵活的，因为可以按任何顺序分配或删除内存。
- 变量可以全局访问。
- 它有助于找到最小和最大的数字。
缺点：
- 与栈相比，堆需要更多的时间来执行。
- 内存管理在堆内存中更为复杂，因为它是全局使用的。
- 堆通常需要更多的时间来计算。
堆数据结构的应用
堆对于查找数组中的最小或最大元素非常有效，并且在顺序统计和选择算法中很有用。从堆中获取最小值/最大值的时间复杂度为O(1) ，（恒定时间复杂度）。
优先级队列是基于堆结构设计的。有效地插入 ( ) 和删除 ( ) 优先级队列中的每个元素需要O(log(n))时间。insert()``delete()
堆实现的优先级队列用于流行的算法，例如：
- 普里姆算法
- Dijkstra 算法
- 堆排序算法
堆中的基本操作
以下是您在实现堆数据结构时可能使用的基本操作：
heapify： 重新排列堆中的元素以保持堆属性。insert： 将一个项目添加到堆中，同时保持其堆属性。delete： 删除堆中的项目。extract： 返回一个项目的值，然后从堆中删除它。isEmpty: boolean，如果 boolean 为空则返回 true，如果有节点则返回 false。size: 返回堆的大小。getMax()： 返回堆中的最大值
如何构建最大堆
最大堆中的元素遵循最大堆属性。这意味着父节点的键总是大于两个子节点的键。要构建最大堆：
- 在堆的开头（根）创建一个新节点。
- 给它赋值。
- 将子节点的值与父节点进行比较。
- 如果父节点的值小于任一子节点（向左或向右）的值，则交换节点。
- 重复直到最大元素位于根父节点（然后你可以说堆属性成立）。
将新元素插入堆时也可以遵循这些步骤。这里的关键是无论在最大堆上执行什么操作，堆属性都必须保持。
移除/删除最大堆中的根节点：
- 删除根节点。
- 将最后一层的最后一个子节点移动到根。
- 将父节点与其子节点进行比较。
- 如果父节点的值小于子节点，则交换它们，并重复直到满足堆属性。
让我们看一下这在代码中是什么样子的。在下一节中，我们将使用[JavaScript] 实现最大堆。
在 JavaScript 中实现最大堆
在我们开始构建最大堆之前，先看看我们将要实现的一些方法以及它们的作用：
_percolateUp()： 将堆属性从子节点恢复到根节点。_maxHeapify()： 将堆属性从特定节点向下恢复到叶节点。insert()： 将给定值附加到堆数组并根据元素的堆属性重新排列元素。在每次插入时，堆均匀增长，大小增加一。getMax()： 返回堆（根节点）中的最大值，不修改堆。注意这里的时间复杂度是常数时间O(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(); 复制代码
如何构建最小堆
直观上，我们可以说最小堆中的元素遵循最小堆属性，因为这与最大堆相反。父节点的键总是小于两个子节点的键。要构建最小堆：
- 在堆的末尾（最后一层）创建一个新的子节点。
- 将新键添加到该节点（将其附加到数组）。
- 向上移动子节点，直到到达根节点并且堆属性得到满足。
删除/删除最小堆中的根节点：
- 删除根节点。
- 将最后一个孩子的钥匙移到根。
- 将父节点与其子节点进行比较。
- 如果父节点的值大于子节点，则交换它们，并重复直到满足堆属性。
在 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()); //you should get -10 let newheap = new minHeap(); let arr = [12, 6, 8, 3, 16, 4, 27]; newheap.buildHeap(arr) //builds this new heap with elements from the array console.log(newheap.getMin()) //this logs 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 } 复制代码
解决方案：
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 } 复制代码
****可以运行上面的代码解决方案。 我们可以将 given 视为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)) --> [ -2, 1, 4, 5, 7, 6, 9 ]
