什么是堆?
- 堆都能用树来表示,一般树的实现都是利用链表。
- 而
二叉堆
是一种特殊的堆,它用完全二叉树来表示,却可以利用数组实现。平时使用最多的是二叉堆。 - 二叉堆易于存储,并且便于索引。
- 堆数据结构像树,但是,是通过数组来实现的(不是通过链表是通过二叉堆)。
- 最小堆就是从小到达排序,最大堆相反。
实现堆
- 因为是数组,所以父子节点的关系就不需要特殊的结构去维护,索引之间通过计算就可以得到,省掉了很多麻烦。如果是链表结构,就会复杂很多。
- 完全二叉树要求叶子节点从左往右填满,才能开始填充下一层,这就保证了不需要对数组整体进行大片的移动。这也是随机存储结构(数组)的短板,即删除一个元素之后,整体往前移是比较费时的。这个特性也导致堆在删除元素的时候,要把最后一个叶子节点补充到树根节点的缘由。
- 二叉堆像树的样子我可以理解,但将他们安排在数组里的话,通过当前下标怎么就能找到父节点和子节点呢?(父节点、左子树和右子树)
- 左子树: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 习题
堆习题