专业定制网站,商丘网站建设方案,网站flash引导页,网站建设类工作描述堆是什么#xff1f;堆都能用树表示#xff0c;并且一般树的实现都是利用链表。平时使用的最多的是二叉堆#xff0c;它可以用完全二叉树表示#xff0c;二叉堆易于存储#xff0c;并且便于索引。在堆的实现时注意#xff1a;因为是数组#xff0c;所以父子节点的关系就… 堆是什么堆都能用树表示并且一般树的实现都是利用链表。平时使用的最多的是二叉堆它可以用完全二叉树表示二叉堆易于存储并且便于索引。在堆的实现时注意因为是数组所以父子节点的关系就不需要特殊的结构去维护了索引之前通过计算就可以得到省掉了很多麻烦如果是链表结构就会复杂很多。 在JavaScript刷题中堆Heap通常用于解决一些需要高效处理优先级的问题例如找出最大或最小的K个元素、实现优先队列等。堆在刷题中的应用场景包括但不限于以下几个方面 找出最大或最小的K个元素通过维护一个大小为K的最大堆或最小堆可以快速找出数组中最大或最小的K个元素。 合并K个有序数组可以使用堆来合并K个有序数组实现高效的合并操作。 实现优先队列堆可以用于实现优先队列保证队列中优先级高的元素先出队。 数组存储二叉堆 二叉堆是一种完全二叉树分为最小堆和最大堆两种类型。用数组存储二叉堆 完全二叉树要求叶子节点从左往右填满才能开始填充下一层。 二叉堆二叉堆是一种完全二叉树通常使用数组来表示。在最小堆中父节点的值小于或等于其子节点的值在最大堆中父节点的值大于或等于其子节点的值。 最小堆在最小堆中父节点的值小于或等于其子节点的值。根节点是堆中的最小值。 最大堆在最大堆中父节点的值大于或等于其子节点的值。根节点是堆中的最大值。 注完全二叉树和满二叉树不同完全二叉树允许叶子节点不铺满。 动画演示创建堆的过程 同一组数据最小堆和最大堆是唯一的吗
同一组数据的最小堆或最大堆不是唯一的。以最小堆为例最小堆是一种特殊的二叉堆它满足以下两个性质
父节点的值小于或等于其子节点的值。堆中任意节点的子树也是一个最小堆。 由于最小堆只要满足上述性质即可因此对于同一组数据可以有多种不同的最小堆表示方式。这是因为在构建最小堆的过程中可以选择不同的节点作为根节点从而得到不同的堆结构。
所以同一组数据的最小堆并不是唯一的可以有多种不同的表示方式。
如何找到节点i父节点和子节点呢 二叉堆在数组是按层次遍历进行存储的从上至下从左至右。因此子节点的index要大于父节点的index。在二叉堆中可以通过以下方式计算父节点和子节点的索引
父节点索引计算对于节点i其父节点的索引为(i-1)/2。左子节点索引计算对于节点i其左子节点的索引为2*i1。右子节点索引计算对于节点i其右子节点的索引为2*i2。
如何删除节点
在删除一个元素之后整体往前移动是比较费时的这也是随机存储结构的短板。因此堆在删除元素的时候是把最后一个叶子节点补充到树根节点。在通过节点移动将堆调整为最小堆或最大堆。
如何通过js构建最大堆 首先构造器得有吧创建一个空的heap数组 其次将获取父节点index、左右子节点index、堆大小size、栈顶元素获取、两节点交换这些简单的辅助函数写一下 主函数insert插入节点每次从heap的尾部也就是最后一个叶子节点插入插进去的叶子节点得向上找它的位置吧写一个up方法找到插入节点位置 up方法实现找到节点的父元素看父元素是否比自己小如果小的换就交换并且递归up方法直到所有元素都调整好。 删除节点pop方法这里依然将最后节点移到第一个跟节点此时根节点一定是最小的不符合最大堆规则所以调整跟节点向下移动写一个down方法移动根节点。这里注意堆的size如果等于1直接删除而不用移动节点。 down方法实现找到根的左右子节点选择比根大的节点进行交换并递归down方法直到所有节点都调整好。 交换节点swap可以使用数组解构进行交换而不用单独定义中间值。 class MaxHeap {constructor() {this.heap [];}//获取父元素下标getParentIndex(index) {return Math.floor((index - 1) / 2);}//获取左子树下标getLeftIndex(index) {return 2 * index 1;}//获取右子树下标getRightIndex(index) {return 2 * index 2;}//获取堆大小size() {return this.heap.length;}//获取堆顶元素peek() {return this.heap[0];}//交换节点swap(id1, id2) {[this.heap[id2], this.heap[id1]] [this.heap[id1], this.heap[id2]];}//插入节点insert(value) {this.heap.push(value);this.up(this.size() - 1);}//删除节点pop() {let last this.heap.pop();if (this.size() 0) return;this.heap[0] last;this.down(0);}//向上移动节点up(index) {const parentIndex this.getParentIndex(index);if (this.heap[index] this.heap[parentIndex]) {this.swap(parentIndex, index);this.up(parentIndex);}}//向下移动节点down(index) {const leftIndex this.getLeftIndex(index);const rightIndex this.getRightIndex(index);let smallIndex index;if (leftIndex this.size() this.heap[leftIndex] this.heap[smallIndex]) {smallIndex leftIndex;}if (rightIndex this.size() this.heap[rightIndex] this.heap[smallIndex]) {smallIndex rightIndex;}if (smallIndex ! index) {this.swap(smallIndex, index);this.down(smallIndex);}}
} 这里让根节点从左右节点中与最小的节点进行交换。注意减少交换次数避免多次递归 如何通过js构建最小堆 与创建最小堆类似。创建堆往堆里新增元素删除堆顶获取堆的父节点下标获取堆左右子节点下标 代码示例
class MinHeap {constructor() {this.heap [];}getParentIndex(index) {return Math.floor((index - 1) / 2);}getLeftIndex(index) {return index * 2 1;}getRightIndex(index) {return index * 2 2;}swap(i1, i2) {[this.heap[i1], this.heap[i2]] [this.heap[i2], this.heap[i1]];}//往堆最后添加节点触发元素上移//当前元素与其跟节点进行比较如果大于其跟节点与根节点进行交换重复操作up(index) {//如果是0就不移动if (index 0) return;//获取父元素const parentIndex this.getParentIndex(index);if (this.heap[parentIndex] this.heap[index]) {this.swap(parentIndex, index);//对交换后parentIndex继续向上递归this.up(parentIndex);}}//从堆顶删除元素时将子节点移到堆顶触发元素下移down(index) {const leftIndex this.getLeftIndex(index);const rightIndex this.getRightIndex(index);let smallIndex index;//左子树小于根节点交换左子树与根if (leftIndex this.size() this.heap[leftIndex] this.heap[smallIndex]) {smallIndex leftIndex;}//同理右子树小于根节点交换右子树与根if (rightIndex this.size() this.heap[rightIndex] this.heap[smallIndex]) {smallIndex rightIndex;}if (smallIndex ! index) {this.swap(smallIndex, index);this.down(smallIndex);}}//往堆里增加元素insert(value) {this.heap.push(value);this.up(this.heap.length - 1);}//将堆顶元素弹出//删除节点pop() {let last this.heap.pop();if (this.size() 0) return;this.heap[0] last;this.down(0);}//获取堆顶peek() {return this.heap[0];}//获取堆大小size() {return this.heap.length;}
} 215. 数组中的第K个最大元素 解决数组中的第K个最大元素问题时通常使用最小堆来实现。通过维护一个大小为K的最小堆可以在O(NlogK)的时间复杂度内找到数组中的第K个最大元素。 但是题目最近新增了一个要求就是必须让算法的时间复杂度控制在O(n)当K很大时使用堆有可能会超出时间复杂度所以要减少不必要的交换移动。 直到今天2024.3.14使用堆排序仍然可以跑通全部案例。 注官方给的快速选择甚至是三数取中的方法来选择基准值也都无法达到时间复杂度会在第40/41个案例卡住。 使用最小堆获取数组中第K个最大元素的思路 初始化一个大小为K的最小堆将数组中的前K个元素放入最小堆中。 遍历数组剩余元素从第K1个元素开始遍历数组对于每个元素如果大于最小堆的堆顶元素堆中最小的元素则将该元素加入最小堆并移除堆顶元素。 返回堆顶元素遍历完成后最小堆的堆顶元素即为数组中的第K个最大元素。 使用最小堆的优势在于可以保持堆的大小为K只需维护K个元素避免了对整个数组进行排序或维护大堆的复杂度。 class MinHeap {constructor() {this.heap [];}getParentIndex(index) {return Math.floor((index - 1) / 2);}getLeftIndex(index) {return index * 2 1;}getRightIndex(index) {return index * 2 2;}swap(i1, i2) {[this.heap[i1], this.heap[i2]] [this.heap[i2], this.heap[i1]];}//往堆最后添加节点触发元素上移//当前元素与其跟节点进行比较如果大于其跟节点与根节点进行交换重复操作up(index) {//如果是0就不移动if (index 0) return;//获取父元素const parentIndex this.getParentIndex(index);if (this.heap[parentIndex] this.heap[index]) {this.swap(parentIndex, index);//对交换后parentIndex继续向上递归this.up(parentIndex);}}//从堆顶删除元素时将子节点移到堆顶触发元素下移down(index) {const leftIndex this.getLeftIndex(index);const rightIndex this.getRightIndex(index);let smallIndex index;//左子树小于根节点交换左子树与根if (leftIndex this.size() this.heap[leftIndex] this.heap[smallIndex]) {smallIndex leftIndex;}//同理右子树小于根节点交换右子树与根if (rightIndex this.size() this.heap[rightIndex] this.heap[smallIndex]) {smallIndex rightIndex;}if (smallIndex ! index) {this.swap(smallIndex, index);this.down(smallIndex);}}//往堆里增加元素insert(value) {this.heap.push(value);this.up(this.heap.length - 1);}//将堆顶元素弹出//删除节点pop() {let last this.heap.pop();if (this.size() 0) return;this.heap[0] last;this.down(0);}//获取堆顶peek() {return this.heap[0];}//获取堆大小size() {return this.heap.length;}
}
// 寻找第 k 个最大的元素
var findKthLargest function (nums, k) {let minHeap new MinHeap();nums.forEach(item {minHeap.insert(item);if (minHeap.size() k) {//每次pop的是栈顶及k1个元素中最小的minHeap.pop();}})return minHeap.peek();
}; 算法可以通过全部的41个测试用例 703. 数据流中的第 K 大元素
设计一个找到数据流中第 k 大元素的类class。注意是排序后的第 k 大元素不是第 k 个不同的元素。
请实现 KthLargest 类
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。int add(int val) 将 val 插入数据流 nums 后返回当前数据流中第 k 大的元素。 思路也是用最小堆来实现最小堆前面已经介绍过堆的插入删除直接将创建堆对象的类拿来用即可。 动态构建一个长度为k的最小堆对顶即第k大的的元素。因为比k小的元素都被pop出去了 /*** param {number} k* param {number[]} nums*/
var KthLargest function (k, nums) {//构建一个k个长度的最小堆this.k k;this.minHeap new MinHeap();// 初始化最小堆for (let num of nums) {this.add(num);}
};/** * param {number} val* return {number}*/
KthLargest.prototype.add function (val) {this.minHeap.insert(val);while (this.minHeap.size() this.k) {this.minHeap.pop();}return this.minHeap.peek();
};/*** Your KthLargest object will be instantiated and called as such:* var obj new KthLargest(k, nums)* var param_1 obj.add(val)*/
class MinHeap {constructor() {this.heap [];}getParentIndex(index) {return Math.floor((index - 1) / 2);}getLeftIndex(index) {return index * 2 1;}getRightIndex(index) {return index * 2 2;}swap(i1, i2) {[this.heap[i1], this.heap[i2]] [this.heap[i2], this.heap[i1]];}//往堆最后添加节点触发元素上移//当前元素与其跟节点进行比较如果大于其跟节点与根节点进行交换重复操作up(index) {//如果是0就不移动if (index 0) return;//获取父元素const parentIndex this.getParentIndex(index);if (this.heap[parentIndex] this.heap[index]) {this.swap(parentIndex, index);//对交换后parentIndex继续向上递归this.up(parentIndex);}}//从堆顶删除元素时将子节点移到堆顶触发元素下移down(index) {const leftIndex this.getLeftIndex(index);const rightIndex this.getRightIndex(index);let smallIndex index;//左子树小于根节点交换左子树与根if (leftIndex this.size() this.heap[leftIndex] this.heap[smallIndex]) {smallIndex leftIndex;}//同理右子树小于根节点交换右子树与根if (rightIndex this.size() this.heap[rightIndex] this.heap[smallIndex]) {smallIndex rightIndex;}if (smallIndex ! index) {this.swap(smallIndex, index);this.down(smallIndex);}}//往堆里增加元素insert(value) {this.heap.push(value);this.up(this.heap.length - 1);}//将堆顶元素弹出//删除节点pop() {let last this.heap.pop();if (this.size() 0) return;this.heap[0] last;this.down(0);}//获取堆顶peek() {return this.heap[0];}//获取堆大小size() {return this.heap.length;}
} 1046. 最后一块石头的重量
有一堆石头每块石头的重量都是正整数。
每一回合从中选出两块 最重的 石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。
最后最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下就返回 0。 思想构建一个最大堆从堆顶取两个值分别为y,x判断如果yx则将y-x放入堆中并将堆调整为最大堆。递归直到堆长度小于2。如果堆里还有值则返回堆顶元素否则为0 /*** param {number[]} stones* return {number}*/
var lastStoneWeight function (stones) {if (stones.length 1) return stones[0];let maxHeap new MaxHeap();stones.forEach((item) maxHeap.insert(item));while (maxHeap.size() 1) {let y maxHeap.peek();maxHeap.pop();let x maxHeap.peek();maxHeap.pop();if (y x) {maxHeap.insert(y - x);}}return maxHeap.size() ? maxHeap.peek() : 0;
};
/*** param {number[]} stones* return {number}*/
var lastStoneWeight function (stones) {if (stones.length 1) return stones[0];let maxHeap new MaxHeap();stones.forEach((item) maxHeap.insert(item));while (maxHeap.size() 1) {let y maxHeap.peek();maxHeap.pop();let x maxHeap.peek();maxHeap.pop();if (y x) {maxHeap.insert(y - x);}}return maxHeap.size() ? maxHeap.peek() : 0;
};
class MaxHeap {constructor() {this.heap [];}//获取父元素下标getParentIndex(index) {return Math.floor((index - 1) / 2);}//获取左子树下标getLeftIndex(index) {return 2 * index 1;}//获取右子树下标getRightIndex(index) {return 2 * index 2;}//获取堆大小size() {return this.heap.length;}//获取堆顶元素peek() {return this.heap[0];}//交换节点swap(id1, id2) {[this.heap[id2], this.heap[id1]] [this.heap[id1], this.heap[id2]];}//插入节点insert(value) {this.heap.push(value);this.up(this.size() - 1);}//删除节点pop() {let last this.heap.pop();if (this.size() 0) return;this.heap[0] last;this.down(0);}//向上移动节点up(index) {const parentIndex this.getParentIndex(index);if (this.heap[index] this.heap[parentIndex]) {this.swap(parentIndex, index);this.up(parentIndex);}}//向下移动节点down(index) {const leftIndex this.getLeftIndex(index);const rightIndex this.getRightIndex(index);let smallIndex index;if (leftIndex this.size() this.heap[leftIndex] this.heap[smallIndex]) {smallIndex leftIndex;}if (rightIndex this.size() this.heap[rightIndex] this.heap[smallIndex]) {smallIndex rightIndex;}if (smallIndex ! index) {this.swap(smallIndex, index);this.down(smallIndex);}}
}
