Open YBFACC opened 4 years ago
可以实现大顶堆或者小顶堆。
可以便利的解决一类 topK 问题。
215. 数组中的第K个最大元素
可视化工具
以小顶堆为例:
根节点小于所有子节点
用列表来模拟树的结构
插入:节点放在数组末尾
插入后与父节点进行比较
若父节点小于子节点,进行交换
重复该操作,直到父节点比子节点小
弹出根节点
将根节点与数组最后一位进行交换
然后pop()弹出当前堆的最小值
进行重建
左右子节点选出最小数
与根节点进行比较
根节点>最小数,交换节点,递归重建
根节点<最小数,结束
function swap(arr, i, j) { ;[arr[i], arr[j]] = [arr[j], arr[i]] } class MinHeap { constructor(arr = []) { this.container = [] if (Array.isArray(arr)) { arr.forEach(this.insert.bind(this)) } } insert(data) { const { container } = this container.push(data) let index = container.length - 1 while (index) { let parent = Math.floor((index - 1) / 2) if (container[index] >= container[parent]) { break } swap(container, index, parent) index = parent } } extract() { const { container } = this if (!container.length) { return null } swap(container, 0, container.length - 1) const res = container.pop() const length = container.length let index = 0, exchange = index * 2 + 1 while (exchange < length) { let right = index * 2 + 2 if (right < length && container[right] < container[exchange]) { exchange = right } if (container[exchange] >= container[index]) { break } swap(container, exchange, index) index = exchange exchange = index * 2 + 1 } return res } top() { if (this.container.length) return this.container[0] return null } } function getMin(arr) { const heap = new MinHeap(arr.slice()) for (let i = 0; i < arr.length; ++i) { console.log(heap.extract()) } } getMin([4, 5, 8, 2, 1, 10, 11, 5, 7, 9, 5, 7])
二叉堆
可以实现大顶堆或者小顶堆。
可以便利的解决一类 topK 问题。
215. 数组中的第K个最大元素
可视化工具
以小顶堆为例:
根节点小于所有子节点
用列表来模拟树的结构
插入:节点放在数组末尾
插入后与父节点进行比较
若父节点小于子节点,进行交换
重复该操作,直到父节点比子节点小
弹出根节点
将根节点与数组最后一位进行交换
然后pop()弹出当前堆的最小值
进行重建
左右子节点选出最小数
与根节点进行比较
根节点>最小数,交换节点,递归重建
根节点<最小数,结束
插入
弹出
代码