数组实现的二叉树，一般实现完全二叉树，一般二叉树不建议使用，根节点下表从 【1】开始

性质

可由数组表示，位置k的节点的父节点位置为[k/2]，而它的两个子节点的位置则分别为2k和2k+1
image.png
image.png

上浮

对一个元素进行上浮，直到到达顶部

  1. function swim(k) {
  2.   while(k > 1 && less(parseInt(k / 2), k)) {
  3.     exch(parseInt(k / 2), k);
  4.     k = parseInt(k / 2);
  5.   }
  6. }

下沉

  1. // N 为数组长度
  3. function sink(k) {
  4.   while(2 * k <= N) {
  5.     let j = 2 * k;
  6.     if (j < N && less(j, j + 1)) j++;
  7.     if(!less(k, j)) break;
  8.     exch(k, j);
  9.     k = j;
  10.   }
  11. }

插入元素

在底部插入元素，并且上浮到合理位置
image.png

删除元素

1.将顶部元素与底部元素对换位置
2.pop()出尾部元素
3.下沉
image.png

实现

  1. /*
  2.  * @Author       : yangte
  3.  * @Date         : 2020-10-10 23:51:41
  4.  * @LastEditTime : 2020-10-11 00:35:19
  5.  * @LastEditors  : yangte
  6.  * @Description  : 数据结构-堆
  7.  */
  8. class Heap {
  9.   constructor() {
  10.     this.pq = [null];
  11.     this.N = 0;
  12.   }
  14.   get isEmpty() {
  15.     return this.N === 0;
  16.   }
  18.   get size() {
  19.     return this.N;
  20.   }
  22.   insert(v) {
  23.     this.pq[++this.N] = v;
  24.     this._swim(this.N);
  25.     console.log(this.pq.join(',').slice(1));
  26.   }
  28.   delMax() {
  29.     this._exch(1, N--);
  30.     this.pq.pop();
  31.     this._sink(1);
  32.   }
  34.   _less(i, j) {
  35.     return this.pq[i] < this.pq[j];
  36.   }
  38.   _exch(i, j) {
  39.     [this.pq[i], this.pq[j]] = [this.pq[j], this.pq[i]];
  40.   }
  41.   // 上浮
  42.   _swim(k) {
  43.     while (k > 1) {
  44.       // 终止条件：子节点小于父节点
  45.       if (this._less(k, Math.floor(k / 2))) break;
  46.       this._exch(Math.floor(k / 2), k);
  47.       k = Math.floor(k / 2);
  48.     }
  49.   }
  51.   _sink(k) {
  52.     while (2 * k <= this.N) {
  53.       let j = 2 * k;
  54.       // 选择子节点：选择走哪条路，左或者右
  55.       if (j < this.N && this._less(j, j + 1)) {
  56.         j++;
  57.       }
  58.       // 终止条件：排序符合正常
  59.       if (this._less(j, k)) break;
  60.       this._exch(k, j);
  61.       k = j;
  62.     }
  63.   }
  64. }