js中堆的操作和案例！

2023-07-09 13:04| 来源: 网络整理| 查看: 265

堆什么是堆？

堆是一种特殊的完全二叉树。完全二叉树的含义就是每层节点都完全填满，除了最后一层外只允许最右边缺少若干个节点。在 JavaScript 中通常用数组表示堆（按照广度优先遍历顺序）。

最大堆在这里插入图片描述

最小堆在这里插入图片描述

特性所有的节点都大于等于它的子节点（最大堆）或者所有的节点都小于等于它的子节点（最小堆）左侧子节点的位置是 2 _ index + 1右侧子节点的位置是 2 _ index + 2 （也就是在左子节点的基础上 + 1）父节点的位置是 (index - 1) / 2 优点高效、快速的找出堆的最大值和最小值，时间复杂度是 O (1)找出第 K 个最大、最小元素常用操作

插入

将值插入堆的底部，即数据的尾部然后上移，将这个值和它父节点进行交换，直到父节点小于等于这个插入的值大小为 k 的堆中插入元素的时间复杂度为 O (logK)

删除堆顶

用数组尾部元素替换堆顶（直接删除堆顶会破坏结构）然后下移，将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶大小为 k 的堆中删除堆顶的时间复杂度为 O (logK)

获取堆顶

返回数组的第 0 项

获取堆大小

返回数组的长度基础案例

通过 Class 实现最小堆

class MinHeap { constructor() { this.heap = [] } top() { return this.heap[0] } size() { return this.heap.length } getChildLeftIndex(i) { return i * 2 + 1 } getChildRightIndex(i) { return i * 2 + 2 } getParentIndex(i) { return (i - 1) >> 1 } swap(index1, index2) { const temp = this.heap[index1] this.heap[index1] = this.heap[index2] this.heap[index2] = temp } 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 leftChildIndex = this.getChildLeftIndex(index) const rightChildIndex = this.getChildRightIndex(index) if (this.heap[leftChildIndex] this.swap(rightChildIndex, index) this.shiftDown(rightChildIndex) } } insert(value) { this.heap.push(value) this.shiftUp(this.heap.length - 1) } pop() { this.heap[0] = this.heap.pop() this.shiftDown(0) } } const h = new MinHeap() h.insert(3) h.insert(2) h.insert(1) h.pop()

原文链接：菜园前端

【本文地址】

js中堆的操作和案例！

js中堆的操作和案例！

今日新闻

推荐新闻