【JavaScript】数据结构之堆

什么是堆？

• 堆都能用树来表示，一般树的实现都是利用链表。
• 而 二叉堆 是一种特殊的堆，它用完全二叉树来表示，却可以利用数组实现。平时使用最多的是二叉堆。
• 二叉堆易于存储，并且便于索引。
• 堆数据结构像树，但是，是通过数组来实现的（不是通过链表是通过二叉堆）。
• 最小堆就是从小到达排序，最大堆相反。

实现堆

• 因为是数组，所以父子节点的关系就不需要特殊的结构去维护，索引之间通过计算就可以得到，省掉了很多麻烦。如果是链表结构，就会复杂很多。
• 完全二叉树要求叶子节点从左往右填满，才能开始填充下一层，这就保证了不需要对数组整体进行大片的移动。这也是随机存储结构（数组）的短板，即删除一个元素之后，整体往前移是比较费时的。这个特性也导致堆在删除元素的时候，要把最后一个叶子节点补充到树根节点的缘由。
• 二叉堆像树的样子我可以理解，但将他们安排在数组里的话，通过当前下标怎么就能找到父节点和子节点呢？（父节点、左子树和右子树）
  • 左子树：index * 2 + 1
  • 右子树：index * 2 + 2
  • 父节点：（ index - 1 ）/ 2

实现最小堆

class MinHeap {constructor() {this.heap = []}// 换位置swap(i1, i2) {let temp = this.heap[i1]this.heap[i1] = this.heap[i2]this.heap[i2] = temp}// 找到父节点getParentIndex(index) {return Math.floor((index - 1) / 2)}// 上（前）移操作up(index) {if (index === 0) returnconst parentIndex = this.getParentIndex(index)if (this.heap[parentIndex] > this.heap[index] ) {this.swap( parentIndex, index )this.up(parentIndex)}}// 找到左侧子节点getLeftIndex(index) {return index * 2 + 1}// 找到右侧子节点getRigthIndex(index) {return index * 2 + 2}// 下（后）移操作down(index) {const leftIndex = this.getLeftIndex(index)const rightIndex = this.getRigthIndex(index)if (this.heap[leftIndex] < this.heap[index]) {this.swap(leftIndex, index)this.down(leftIndex)}if (this.heap[rightIndex] < this.heap[index]) {this.swap(rightIndex, index)this.down(rightIndex)}}// 添加元素insert( value ) {this.heap.push(value)this.up( this.heap.length-1 )}// 删除堆顶pop() {this.heap[0] = this.heap.pop()this.down(0)}// 获取堆顶peek() {return this.heap[0]}// 获取堆长度size() {return this.heap.length}
}let arr = new MinHeap()
arr.insert(5)
arr.insert(4)
arr.insert(6)
arr.insert(1)
arr.pop()
console.log(arr)
console.log(arr.size())
console.log(arr.peek())

leetcode 习题

堆习题