堆是什么？

• 堆是一种特殊的完全二叉树
• 所有的节点都大于等于（最大堆）或小于等于（最小堆）它的子节点。

js 中的堆

• js 中通常用数组表示堆
• 左侧子节点的位置是 2 * index + 1
• 右侧子节点的位置是2* index + 2
• 父节点位置是（index - 1）/ 2

堆的应用

• 堆能高效、快速的找出最大值和最小值，时间复杂度O(1)。
• 找出第K个最大（小）元素。

第K个最大元素

构建一个最小堆，并将元素依次插入堆中。

当堆的容量超过K，就是删除堆顶。

插入结束后，堆顶就是第K个最大元素。

JavaScript实现：最小堆类

 

实现步骤

在类里，声明一个数组，用来装元素。

主要方法： 插入、删除堆顶、获取堆顶、获取堆大小。

 

代码实现

class MianHeap {
				constructor() {
					this.heap = []
				}
				swap(i1, i2) { // 切换位置
					const temp = this.heap[i1];
					this.heap[i1] = this.heap[i2]
					this.heap[i2] = temp
				}
				getParentIndex(i) { // 找到父节点位置
					return (i - 1) >> 1; //Math.floor((i - 1 ) / 2)

				}
				getLeftIndex(i) { // 获取左节点
					return i * 2 + 1
				}
				getRightIndex(i) { // 获取有节点
					return i * 2 + 2
				}
				shiftUp(index) {
					if (index == 0) {
						return
					}
					const parentIndex = this.getParentIndex(index);
					if (this.heap[parentIndex] > this.heap[index]) {
						this.swap(parentIndex, index);
						this.shiftUp(parentIndex)
					}
				}
				shiftDown(index) {
					const leftIndex = this.getLeftIndex(index)
					const rightIndex = this.getRightIndex(index)
					if (this.heap[leftIndex] < this.heap[index]) {
						this.swap(leftIndex, index);
						this.shiftDown(leftIndex)
					}
					if (this.heap[rightIndex] < this.heap[index]) {
						this.swap(rightIndex, index);
						this.shiftDown(rightIndex)
					}
				}
				inseter(value) {
					this.heap.push(value)
					this.shiftUp(this.heap.length - 1)
				}
				pop() {
					this.heap[0] = this.heap.pop();
					this.shiftDown(0);
				}
				peek() {
					return this.heap[0];
				}
				size() {
					return this.heap.length
				}
			}