江苏龙网

  1. 主页 > 生活百科 > >

如何构建最小和最大堆( 二 )

堆

  • 将最后一层的最后一个子节点移动到根 。
  • 将父节点与其子节点进行比较 。
  • 如果父节点的值小于子节点，则交换它们 ， 并重复直到满足堆属性 。
    • 让我们看一下代码中的样子 。我们将使用JAVAScript实现最大堆 。
    在 JavaScript 中实现最大堆在我们开始构建最大堆之前，先看一下我们将实现的一些方法及其用途：
    • _percolateUp()：将堆属性从子节点恢复到根节点 。
    • _maxHeapify()：将堆属性从特定节点恢复到叶节点 。
    • insert()：将给定值附加到堆数组并根据元素的堆属性重新排列元素 。在每个新插入中 ， 堆均匀增长，并且大小增加一 。
    • getMax()：返回堆（根节点）中的最大值 ， 不修改堆 。注意这里的时间复杂度是常数时间氧（1）欧（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)returnelse 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 = rightelse 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();如何构建最小堆直观上，我们可以说最小堆中的元素遵循最小堆属性，因为这与最大堆相反 。父节点的键始终小于两个子节点的键 。为了构建最小堆，我们：
    • 在堆的末尾（最后一层）创建一个新的子节点 。
    • 将新键添加到该节点（将其附加到数组） 。
    • 向上移动子节点 ， 直到到达根节点并且满足堆属性 。
    要移除/删除最小堆中的根节点：
    • 删除根节点 。
    • 将最后一个子项的密钥移至 root 。
    • 将父节点与其子节点进行比较 。
    • 如果父节点的值大于子节点，则交换它们，并重复直到满足堆属性 。
    在 JavaScript 中实现最小堆在我们开始构建最小堆之前，请注意它的实现与最大堆类似 。minHeapify()恢复堆属性 。getMin()返回堆（根节点）中的最小值，而不修改堆 。并removeMin()删除最小值并返回它 。
    class minHeap {constructor() {this.heap = []this.elements = 0;};insert(val) {if (this.elements >== this.heap.length) {this.elements = this.elements + 1this.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)returnelse 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())


    推荐阅读


    上一篇：MySQL数据删除绝招，轻松搞定数据清除

    下一篇：.NET Core中一些优秀的项目和框架