数据结构在计算机编程中非常重要，可以快速有效地组织、管理和存储数据。数据结构对于任何开发人员来说都是其工具包中绝对必要的技能。
此篇文章重点关注堆，这是一种特殊的基于树的数据结构，它实现了完整的二叉树。
堆使用完全二叉树来避免数组中出现漏洞。完全二叉树是每个节点最多有两个子节点的树，除了叶节点可以为空之外，所有级别的节点都是满的。堆是根据堆属性构建的，它将父节点键与其子节点键进行比较。
在本文的后面部分，我们将详细讨论基于最小堆属性构建的最小堆和基于最大堆属性构建的最大堆。
需要注意的是，堆并不总是排序的，它们遵循的关键条件是最大或最小元素放置在根节点（顶部）上，具体取决于它是最大堆还是最小堆。堆数据结构与堆内存不同。
优点：
缺点：
堆对于查找数组中的最小或最大元素非常有效，并且对于顺序统计和选择算法很有用。从堆中获取最小值/最大值的时间复杂度为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.28at.com/showinfo-26-22482-0.html如何构建最小和最大堆
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com
Copyright © 2016-2023 天津谷骐科技有限公司 版权所有 sitemap.xml
违法及侵权请联系：2376512515@qq.com 津ICP备18001702号
津公网安备 12010102000574号
