二叉堆基本数据结构

二叉堆（Binary Heap）没什么神秘，性质比二叉搜索树 BST 还简单。
其主要操作就两个，sink（下沉）和 swim（上浮），用以维护二叉堆的性质。
其主要应用有两个，首先是一种排序方法「堆排序」，第二是一种很有用的数据结构「优先级队列」。

https://zhuanlan.zhihu.com/p/113593148

堆的底层实际上是一棵完全二叉树，可以用数组实现

  • 每个的节点元素值不小于其子节点 - 最大堆
  • 每个的节点元素值不大于其子节点 - 最小堆

image.png

堆用一般用数组展示如下：

  1. 如果根节点在数组中的位置是1，第n个位置的子节点分别在2_n 与 2_n+1，第n个位置的双亲节点分别在⌊i /2⌋。因此，第1个位置的子节点在2和3.

  2. 如果根节点在数组中的位置是0，第n个位置的子节点分别在2_n+1与2_n+2，第n个位置的双亲节点分别在⌊（i-1） /2⌋。因此，第0个位置的子节点在1和2.

image.png

image.png

我们以大顶堆为例实现：

插入：上移
在数组的最末尾插入新节点，然后自下而上地调整子节点与父节点的位置：比较当前结点与父节点的大小，若不满足大顶堆的性质，则交换两节点，从而使当前子树满足二叉堆的性质。时间复杂度为O(logn)。
image.png
删除：下沉
image.png

  1. class Heap {
  2.     constructor() {
  3.         this.data = [];
  4.     }
  5.     /**
  6.      * js中以0作为数组的索引
  7.      * i的父节点为 Math.floor((i-1) / 2)
  8.      * i的左子节点为 nLeftIndex = 2 * (i + 1) - 1;  // 2i+1
  9.      * i的右子节点为 nRightIndex = 2 * (i + 1);     // 2i+2
  10.      */
  11.     insert(value) {
  12.         this.data.push(value);
  13.         let nIndex = this.data.length - 1;
  14.         let nFatherIndex = Math.floor((nIndex - 1 ) / 2);
  15.         while(nFatherIndex >= 0) {
  16.             if(this.data[nIndex] > this.data[nFatherIndex]) {
  17.                 const temp =  this.data[nFatherIndex];
  18.                 this.data[nFatherIndex] = this.data[nIndex];
  19.                 this.data[nIndex] = temp;
  20.             }
  21.             nIndex = nFatherIndex;
  22.             nFatherIndex = Math.floor((nIndex - 1 ) / 2);
  23.         }
  25.     }
  26.     // 删除最大的节点
  27.     delete() {
  28.         let nIndex = 0;
  29.         let nLeaf = this.data.pop();
  30.         // 将最后一个子节点补充到根节点
  31.         this.data[nIndex] = nLeaf;
  32.         let len = this.data.length - 1;
  33.         while(nIndex <=len) {
  34.             let nLeftIndex = 2 * (nIndex + 1) - 1;
  35.             let nRightIndex = 2 * (nIndex + 1);
  36.             let nSelectIndex = nLeftIndex;
  37.             // 找到最大的子节点
  38.             if(nRightIndex  <= len) {
  39.                 nSelectIndex = this.data[nLeftIndex] > this.data[nRightIndex] ? nLeftIndex : nRightIndex;
  40.             }
  41.             if(nSelectIndex <= len && this.data[nIndex] < this.data[nSelectIndex]) {
  42.                 var temp = this.data[nIndex];
  43.                 this.data[nIndex] = this.data[nSelectIndex];
  44.                 this.data[nSelectIndex] = temp;
  45.             }
  46.             nIndex = nSelectIndex;
  47.         }
  48.     }
  49.     print() {
  50.         console.log(this.data);
  51.     }
  52.     build(arr) {
  53.         this.data = [];
  54.         for(let i = 0; i < arr.length; i++) {
  55.             this.insert(arr[i]);
  56.         }
  57.     }
  58. }
  60. const heap = new Heap();
  61. heap.build([1, 3, 4, 2]);
  62. heap.print(); // [ 4, 2, 3, 1 ]
  63. heap.delete();
  64. heap.print(); // [ 3, 2, 1 ]

练习

215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

var findKthLargest = function (nums, k) {
  let minHeap = new MinHeap()
  for (let i = 0; i < nums.length; i++) {
    if (minHeap.size() < k) minHeap.push(nums[i])
    else if (minHeap.top() < nums[i]) {
      minHeap.pop()
      minHeap.push(nums[i])
    }
  }
  return minHeap.top()
};

参考

二叉堆：https://labuladong.github.io/algo/2/18/45/
https://zhuanlan.zhihu.com/p/113593148

堆排序：https://www.cnblogs.com/lanhaicode/p/10546257.html