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