Open ChuChencheng opened 4 years ago
本质上是完全二叉树
分为两种类型
堆内部能实现自我调整,对于二叉堆有以下操作:
当插入一个节点到二叉堆中,首先将节点插入到二叉堆的末尾,然后进行“上浮”操作 从末尾节点开始,与其父节点进行比较,以最小堆为例,如果插入的节点小于父节点,则与父节点的位置进行交换,重复该步骤,直到节点到达合适的位置,即大于或等于其父节点
当要从二叉堆中删除节点,将堆顶(即二叉树根节点)元素删除,然后将末尾的元素移动到堆顶 这时堆顶元素的位置不一定是正确的,需要做一个“下沉”操作 从堆顶元素开始,与其左右子节点进行比较,如果当前节点比左右子节点大,则与最小的子节点进行交换,直到节点到达合适的位置,即节点小于或等于其左右子节点
初始化二叉堆,可以看成是把一个无序的二叉堆调整为有序的二叉堆的过程,只需要对于所有非子节点进行“下沉”操作,即可生成一个有序的二叉堆
二叉堆的存储结构不用链表,而是可以直接用一个数组来存储。 其中,第一个元素即为堆顶 对于节点 n 来说, 其左子节点的索引为 2 * n + 1 右子节点索引为 2 * n + 2 父节点索引为 Math.floor((n - 1) / 2)
2 * n + 1
2 * n + 2
Math.floor((n - 1) / 2)
二叉堆的最后一个非叶子节点的索引为 Math.floor((length - 2) / 2)
Math.floor((length - 2) / 2)
/** 最小堆 */ class BinaryHeap { private heap: number[] = [] constructor (elements: number[]) { this.heap = elements // 构建二叉堆,对每个非叶子节点进行“下沉”操作 for (let i = Math.floor((this.heap.length - 2) / 2); i >= 0; i--) { this.down(i) } } /** 插入 */ insert (value: number) { this.heap.push(value) this.up() } /** 删除 */ delete () { this.heap.shift() const last = this.heap.pop() if (last != null) { this.heap.unshift(last) this.down() } } /** 上浮 */ up () { let n = this.heap.length - 1 if (n <= 0) return const target = this.heap[n] let parentIndex = Math.floor((n - 1) / 2) // 如果父节点大于子节点,则将父节点复制到子节点的位置,当前父节点的位置可以复制为上浮节点的值,但是还需要继续往上寻找目标位置,所以可以先不用赋值,等循环结束后再在目标位置赋值为上浮的节点;然后继续往上寻找,直到不符合条件,即找到了上浮节点的目标位置 while (parentIndex > 0 && this.heap[parentIndex] > target) { this.heap[n] = this.heap[parentIndex] n = parentIndex parentIndex = Math.floor((n - 1) / 2) } this.heap[n] = target } /** 下沉 */ down (n: number = 0) { const target = this.heap[n] let parentIndex = n let leftChildIndex = 2 * n + 1 const length = this.heap.length while (leftChildIndex < length) { // 这里定义最小的子节点,可以直接用 leftChildIndex ,为了方便阅读,多定义一个变量 let minChildIndex = leftChildIndex const rightChildIndex = leftChildIndex + 1 if (rightChildIndex < length && this.heap[rightChildIndex] < this.heap[leftChildIndex]) { minChildIndex = rightChildIndex } // 如果最小的子节点都大于待下沉的节点,说明下沉节点已经到达目标位置 if (this.heap[minChildIndex] >= target) break // 否则将最小子节点的值复制到它的父节点上,下沉节点的值最后循环退出后再复制到目标位置 this.heap[parentIndex] = this.heap[minChildIndex] parentIndex = minChildIndex leftChildIndex = 2 * parentIndex + 1 } this.heap[parentIndex] = target } }
漫画:什么是二叉堆?
概念
本质上是完全二叉树
分为两种类型
特性
堆内部能实现自我调整,对于二叉堆有以下操作:
插入节点
当插入一个节点到二叉堆中,首先将节点插入到二叉堆的末尾,然后进行“上浮”操作 从末尾节点开始,与其父节点进行比较,以最小堆为例,如果插入的节点小于父节点,则与父节点的位置进行交换,重复该步骤,直到节点到达合适的位置,即大于或等于其父节点
删除节点
当要从二叉堆中删除节点,将堆顶(即二叉树根节点)元素删除,然后将末尾的元素移动到堆顶 这时堆顶元素的位置不一定是正确的,需要做一个“下沉”操作 从堆顶元素开始,与其左右子节点进行比较,如果当前节点比左右子节点大,则与最小的子节点进行交换,直到节点到达合适的位置,即节点小于或等于其左右子节点
构建二叉堆
初始化二叉堆,可以看成是把一个无序的二叉堆调整为有序的二叉堆的过程,只需要对于所有非子节点进行“下沉”操作,即可生成一个有序的二叉堆
数据结构
二叉堆的存储结构不用链表,而是可以直接用一个数组来存储。 其中,第一个元素即为堆顶 对于节点 n 来说, 其左子节点的索引为
2 * n + 1
右子节点索引为2 * n + 2
父节点索引为Math.floor((n - 1) / 2)
二叉堆的最后一个非叶子节点的索引为
Math.floor((length - 2) / 2)
实现
参考
漫画:什么是二叉堆?