概念

首先，数据结构中的堆和堆内存完全不是一个东西。
参考知乎回答：https://www.zhihu.com/question/276016774/answer/385381844

这里，我们讨论数据结构：堆，英文叫，Heap。
堆是一种完全二叉树，它的特点是任何一个节点的子节点一定比其父节点大（或者小），如果整棵树都是比父节点大，它是一个最小堆，反之，则是最大堆。
image.png
这里需要理解的是，

  • 逻辑上，堆是一棵树，完全二叉树（就是除了最后一层节点外，上面的层次是一棵满二叉树）。
  • 另外，堆的每一对父子节点顺序是有要求的，要么都是大于关系，要么都是小于关系。

堆的实现

数据结构

从逻辑上来讲，堆是一棵树。但是完全二叉树可以用数组来表示。
比如上面图中所表示的堆，用数组表示就是:
数组：[ 6, 5, 3, 4, 2, 1 ]
下标： 0 1 2 3 4 5
现在要说的是，关于数组表示完全二叉树，有两个重要公式：
任意节点下标index而言， 它的父节点下标是：取整(index - 1 / 2)；它的左边子节点是：index 2 + 1;它的右边子节点是：index 2 + 2；

就上面那幅图而言，我们用值是‘5’的节点举例子：
它的下标是1，那么父节点下标 （1 - 0） / 2， 取整为0，没问题，
左边子节点： 2 1 + 1 = 3，没问题，右边 2 1 + 2 = 4 ，也ok。

插入元素算法

堆的数据结构有个特点，就是我们在做任何增加删除操作的时候，都要维持堆的结构，就是保持父子节点的大小关系。
堆插入的算法思想是这样：
先向数组尾部追加一个元素。
找到这个元素的父元素，比较这个元素和父元素的大小关系是否正确，如果正确，那ok，按兵不动。如果不正确，那就要交换父元素和该元素，然后再比较新的父元素，这个过程可能持续到直到一直换到堆顶。
也就是说，最慢情况是，有多少层换了多少次。
n个节点的堆有log(n)层，所以时间复杂度，O(log(n))

删除堆顶算法

删除堆顶的操作，我们的思想是：
先把堆中最后一个元素的弹出，把它的值设置为堆顶。
这时候，堆的稳定性破坏了，但是除了堆顶，其他的节点都ok。
所以，堆顶和它的子节点比较，如果不符合大小关系就换一下，换了以后和新的子节点再比较，不行再换….最终我们就得到删除堆顶以后的一个新的堆。
时间复杂度，依旧，O(log(n))

实现，用TS以及可以做的更多

用TS实现了一个最小堆，不过既然用TS了，那就可以做很多事情了：

  2. /**
  3.  * 简单实现最小堆类
  4.  */
  5. class MinHeap {
  6.   private heap: Array<number>;
  8.   constructor() {
  9.     this.heap = [];
  10.   }
  12.   // 交换两个元素
  13.   private swap(aIndex: number, bIndex: number) {
  14.     const tmp = this.heap[aIndex];
  15.     this.heap[aIndex] = this.heap[bIndex];
  16.     this.heap[bIndex] = tmp;
  17.   }
  19.   // 得到父节点公式是：子节点下标 - 1 / 2，取整
  20.   private getParentIndex(index: number) {
  21.     return Math.floor((index - 1) / 2);
  22.   }
  24.   // 得到左右子节点公式
  25.   // 左子 = index * 2 + 1
  26.   // 右子 = index * 2 + 2
  27.   private getLeftChildIndex(index: number) {
  28.     return index * 2 + 1;
  29.   }
  31.   private getRightChildIndex(index: number) {
  32.     return index * 2 + 2;
  33.   }
  35.   // 上移到合适的位置的方法
  36.   // 和父节点交换
  37.   private shiftUp(index: number) {
  38.     if (index === 0) return;
  39.     const parentIndex = this.getParentIndex(index);
  40.     if (this.heap[index] < this.heap[parentIndex]) {
  41.       this.swap(index, parentIndex);
  42.       this.shiftUp(parentIndex);
  43.     }
  44.   }
  46.   // 下沉到正确的位置
  47.   // 和子节点交换
  48.   private shiftDown(index: number) {
  49.     const leftChildIndex = this.getLeftChildIndex(index);
  50.     const rightChildIndex = this.getRightChildIndex(index);
  51.     if(this.heap[index] > this.heap[leftChildIndex]) {
  52.       this.swap(index, leftChildIndex);
  53.       this.shiftDown(leftChildIndex);
  54.     }
  56.     if(this.heap[index] > this.heap[rightChildIndex]){
  57.       this.swap(index, rightChildIndex);
  58.       this.shiftDown(rightChildIndex);
  59.     }
  60.   }
  62.   /**
  63.    * 插入的方法
  64.    * 先插入，后上移动到合适的位置
  65.    */
  66.   public insert(value: number) {
  67.     // 先插入
  68.     this.heap.push(value);
  69.     // 上移
  70.     this.shiftUp(this.heap.length - 1);
  71.   }
  73.   /**
  74.    * 删除堆顶的方法
  75.    * 先把最后一个元素放在堆顶
  76.    * 然后让堆顶元素下沉到合适位置
  77.    */
  78.   public pop() {
  79.     if (this.heap.length === 1) {
  80.       this.heap.pop();
  81.       return;
  82.     }
  83.     const last = this.heap.pop();
  84.     if (last) {
  85.       this.heap[0] = last;
  86.       this.shiftDown(0);
  87.     }
  88.   }
  90.   /**
  91.    * 得到对顶元素的值
  92.    */
  93.   public peak() {
  94.     return this.heap[0];
  95.   }
  97.   /**
  98.    * 得到堆的大小
  99.    */
  100.   public size() {
  101.     return this.heap.length;
  102.   }
  104. }
  108. //////////// test
  109. const h = new MinHeap();
  111. h.insert(3);
  112. h.insert(2);
  114. h.insert(1);
  115. h.insert(10);
  117. h.pop()

这里有一个番外篇：实战：TS面向对象实现堆数据结构（Heap） （写于等飞机时）

面试题

待补充