数据结构-堆
堆定义
- 堆的应用
- 第K个最大元素
- 第K个最小元素 -> 只需将最小堆改为最大堆即可
JavaScript 实现:最小堆类
插入堆
code
class MinHeap {
constructor() { // 声明在构造函数
this.heap = []; // 建立一个空数组用来存放堆
}
swap(i1, i2){ // 8. 封装一个交换函数
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
getParentIndex(i){ // 4. 封装获取 当前节点的父节点 的方法
return Math.floor( (i - 1) / 2 ); // Math.floor取商的操作
}
shiftUp(index){ // 3. 封装上移操作的方法
if(index === 0){return}; // 10. 若上移至堆顶则停止上移
const parentIndex = this.getParentIndex(index); // 5. 获取父节点
if(this.heap[parentIndex] > this.heap[index]){ // 6. 若父节点的值大于该节点的值则需要交换
this.swap(parentIndex, index); // 7. 封装一个交换函数
this.shiftUp(parentIndex); // 9. 交换之后继续执行上移操作
}
}
insert(value) { // 1. 封装插入堆方法
this.heap.push(value);
this.shiftUp(this.heap.length - 1); // 2. 封装一个上移操作的函数, 传入最后一个元素
}
}
// 验证
const h = new MinHeap(); // 声明一个实例化对象
h.insert(3);
h.insert(2);
h.insert(1);
// 执行完 h 中的元素是 [1, 3, 2]
删除堆
code
class MinHeap {
constructor() { // 声明在构造函数
this.heap = []; // 建立一个空数组用来存放堆
}
swap(i1, i2){ // 8. 封装一个交换函数
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
getParentIndex(i){ // 4. 封装获取 当前节点的父节点 的方法
return Math.floor( (i - 1) / 2 ); // Math.floor取商的操作
}
getLeftIndex(i){ // 14. 封装获取 当前节点的左子节点 的方法
return 2 * i + 1;
}
getRightIndex(i){ // 15. 封装获取 当前节点的右子节点 的方法
return 2 * i + 2;
}
shiftUp(index){ // 3. 封装上移操作的方法
if(index === 0){return}; // 10. 若上移至堆顶则停止上移
const parentIndex = this.getParentIndex(index); // 5. 获取父节点
if(this.heap[parentIndex] > this.heap[index]){ // 6. 若父节点的值大于该节点的值则需要交换
this.swap(parentIndex, index); // 7. 封装一个交换函数
this.shiftUp(parentIndex); // 9. 交换之后继续执行上移操作
}
}
shiftDown(index){ // 13. 封装下移操作的方法 因要与子节点交换，故封装两个获取子节点的方法
const leftIndex = this.getLeftIndex(index); // 16. 获取左侧子节点
const rightIndex = this.getRightIndex(index); // 17. 获取右侧子节点
if(this.heap[leftIndex] < this.heap[index]){ // 18. 若左子节点值小于当前节点的值则交换
this.swap(leftIndex, index);
this.shiftDown(leftIndex); // 19. 交换之后继续执行下移操作
}
// 20. 右侧子节点相同的操作
if(this.heap[rightIndex] < this.heap[index]){ // 18. 若右子节点值小于当前节点的值则交换
this.swap(rightIndex, index);
this.shiftDown(rightIndex); // 19. 交换之后继续执行下移操作
}
}
insert(value) { // 1. 封装插入堆方法
this.heap.push(value);
this.shiftUp(this.heap.length - 1); // 2. 封装一个上移操作的函数, 传入最后一个元素
}
pop(){ // 11. 封装删除堆的方法
this.heap[0] = this.heap.pop(); // 将最后一个元素删除并替换堆顶元素
this.shiftDown(0); // 12. 封装一个下移操作的方法
}
}
// 验证
const h = new MinHeap(); // 声明一个实例化对象
// 插入操作
h.insert(3);
h.insert(2);
h.insert(1);
// 删除堆顶元素
h.pop();
获取堆顶和堆的大小
peek(){ // 21. 获取堆顶元素
return this.heap[0];
}
size(){ // 31. 获取堆的大小
return this.heap.length;
}
完整最小堆代码
class MinHeap {
constructor() { // 声明在构造函数
this.heap = []; // 建立一个空数组用来存放堆
}
swap(i1, i2){ // 8. 封装一个交换函数
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
getParentIndex(i){ // 4. 封装获取 当前节点的父节点 的方法
return Math.floor( (i - 1) / 2 ); // Math.floor取商的操作
}
getLeftIndex(i){ // 14. 封装获取 当前节点的左子节点 的方法
return 2 * i + 1;
}
getRightIndex(i){ // 15. 封装获取 当前节点的右子节点 的方法
return 2 * i + 2;
}
shiftUp(index){ // 3. 封装上移操作的方法
if(index === 0){return}; // 10. 若上移至堆顶则停止上移
const parentIndex = this.getParentIndex(index); // 5. 获取父节点
if(this.heap[parentIndex] > this.heap[index]){ // 6. 若父节点的值大于该节点的值则需要交换
this.swap(parentIndex, index); // 7. 封装一个交换函数
this.shiftUp(parentIndex); // 9. 交换之后继续执行上移操作
}
}
shiftDown(index){ // 13. 封装下移操作的方法 因要与子节点交换，故封装两个获取子节点的方法
const leftIndex = this.getLeftIndex(index); // 16. 获取左侧子节点
const rightIndex = this.getRightIndex(index); // 17. 获取右侧子节点
if(this.heap[leftIndex] < this.heap[index]){ // 18. 若左子节点值小于当前节点的值则交换
this.swap(leftIndex, index);
this.shiftDown(leftIndex); // 19. 交换之后继续执行下移操作
}
// 20. 右侧子节点相同的操作
if(this.heap[rightIndex] < this.heap[index]){ // 18. 若右子节点值小于当前节点的值则交换
this.swap(rightIndex, index);
this.shiftDown(rightIndex); // 19. 交换之后继续执行下移操作
}
}
insert(value) { // 1. 封装插入堆方法
this.heap.push(value);
this.shiftUp(this.heap.length - 1); // 2. 封装一个上移操作的函数, 传入最后一个元素
}
pop(){ // 11. 封装删除堆的方法
this.heap[0] = this.heap.pop(); // 将最后一个元素删除并替换堆顶元素
this.shiftDown(0); // 12. 封装一个下移操作的方法
}
peek(){ // 21. 获取堆顶元素
return this.heap[0];
}
size(){ // 31. 获取堆的大小
return this.heap.length;
}
}
// 验证
const h = new MinHeap(); // 声明一个实例化对象
// 插入操作
h.insert(3); // 此处设置调试断点
h.insert(2);
h.insert(1);
// 删除堆顶元素
h.pop();
刷题
LeetCode: 215. 数组中的第K个最大元素
题目描述
解题思路
解题步骤
Code
class MinHeap {
constructor() { // 声明在构造函数
this.heap = []; // 建立一个空数组用来存放堆
}
swap(i1, i2){ // 8. 封装一个交换函数
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
getParentIndex(i){ // 4. 封装获取 当前节点的父节点 的方法
return Math.floor( (i - 1) / 2 ); // Math.floor取商的操作
}
getLeftIndex(i){ // 14. 封装获取 当前节点的左子节点 的方法
return 2 * i + 1;
}
getRightIndex(i){ // 15. 封装获取 当前节点的右子节点 的方法
return 2 * i + 2;
}
shiftUp(index){ // 3. 封装上移操作的方法
if(index === 0){return}; // 10. 若上移至堆顶则停止上移
const parentIndex = this.getParentIndex(index); // 5. 获取父节点
if(this.heap[parentIndex] > this.heap[index]){ // 6. 若父节点的值大于该节点的值则需要交换
this.swap(parentIndex, index); // 7. 封装一个交换函数
this.shiftUp(parentIndex); // 9. 交换之后继续执行上移操作
}
}
shiftDown(index){ // 13. 封装下移操作的方法 因要与子节点交换，故封装两个获取子节点的方法
const leftIndex = this.getLeftIndex(index); // 16. 获取左侧子节点
const rightIndex = this.getRightIndex(index); // 17. 获取右侧子节点
if(this.heap[leftIndex] < this.heap[index]){ // 18. 若左子节点值小于当前节点的值则交换
this.swap(leftIndex, index);
this.shiftDown(leftIndex); // 19. 交换之后继续执行下移操作
}
// 20. 右侧子节点相同的操作
if(this.heap[rightIndex] < this.heap[index]){ // 18. 若右子节点值小于当前节点的值则交换
this.swap(rightIndex, index);
this.shiftDown(rightIndex); // 19. 交换之后继续执行下移操作
}
}
insert(value) { // 1. 封装插入堆方法
this.heap.push(value);
this.shiftUp(this.heap.length - 1); // 2. 封装一个上移操作的函数, 传入最后一个元素
}
pop(){ // 11. 封装删除堆的方法
this.heap[0] = this.heap.pop(); // 将最后一个元素删除并替换堆顶元素
this.shiftDown(0); // 12. 封装一个下移操作的方法
}
peek(){ // 21. 获取堆顶元素
return this.heap[0];
}
size(){ // 31. 获取堆的大小
return this.heap.length;
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
const h = new MinHeap();
nums.forEach( n => {
h.insert(n); // 不断往最小堆里面添加元素
if(h.size() > k){ // 若超过 k 的大小则执行删除堆顶元素
h.pop();
}
})
return h.peek(); // 返回堆顶元素
};
时间复杂度 空间复杂度分析
因其中有forEach且堆里面的上移下移操作都是
Olog(n)，所以****时间复杂度****为Onlog(n)因堆大小由数组K决定，所以****空间复杂度****为
O(k)
LeetCode: 347. 前 K 个高频元素
题目描述
Code1
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
const map = new Map();
nums.forEach( n => {
map.set(n, map.has(n) ? map.get(n) + 1 : 1);
})
// console.log(map);
// 排序
const list = Array.from(map).sort((a, b)=>{b[1] - a[1]});
// console.log(list);
return list.slice(0, k).map( n=> n[0] );
};
#### 时间复杂度 空间复杂度分析
- 因其中有排序算法最快也是log(n),加上外侧的循环，所以****时间复杂度****为Onlog(n),不满足题目要求，故要改写
code2
class MinHeap {
constructor() { // 声明在构造函数
this.heap = []; // 建立一个空数组用来存放堆
}
swap(i1, i2){ // 8. 封装一个交换函数
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
getParentIndex(i){ // 4. 封装获取 当前节点的父节点 的方法
return Math.floor( (i - 1) / 2 ); // Math.floor取商的操作
}
getLeftIndex(i){ // 14. 封装获取 当前节点的左子节点 的方法
return 2 * i + 1;
}
getRightIndex(i){ // 15. 封装获取 当前节点的右子节点 的方法
return 2 * i + 2;
}
shiftUp(index){ // 3. 封装上移操作的方法
if(index === 0){return}; // 10. 若上移至堆顶则停止上移
const parentIndex = this.getParentIndex(index); // 5. 获取父节点
if(this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val){ // 6. 若父节点的值大于该节点的值则需要交换
this.swap(parentIndex, index); // 7. 封装一个交换函数
this.shiftUp(parentIndex); // 9. 交换之后继续执行上移操作
}
}
shiftDown(index){ // 13. 封装下移操作的方法 因要与子节点交换，故封装两个获取子节点的方法
const leftIndex = this.getLeftIndex(index); // 16. 获取左侧子节点
const rightIndex = this.getRightIndex(index); // 17. 获取右侧子节点
if(this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val){ // 18. 若左子节点值小于当前节点的值则交换
this.swap(leftIndex, index);
this.shiftDown(leftIndex); // 19. 交换之后继续执行下移操作
}
// 20. 右侧子节点相同的操作
if(this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val){ // 18. 若右子节点值小于当前节点的值则交换
this.swap(rightIndex, index);
this.shiftDown(rightIndex); // 19. 交换之后继续执行下移操作
}
}
insert(value) { // 1. 封装插入堆方法
this.heap.push(value);
this.shiftUp(this.heap.length - 1); // 2. 封装一个上移操作的函数, 传入最后一个元素
}
pop(){ // 11. 封装删除堆的方法
this.heap[0] = this.heap.pop(); // 将最后一个元素删除并替换堆顶元素
this.shiftDown(0); // 12. 封装一个下移操作的方法
}
peek(){ // 21. 获取堆顶元素
return this.heap[0];
}
size(){ // 31. 获取堆的大小
return this.heap.length;
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
const map = new Map();
nums.forEach( n => {
map.set(n, map.has(n) ? map.get(n) + 1 : 1);
})
const h = new MinHeap();
map.forEach((val, key) => {
h.insert({ val, key });
if(h.size() > k){
h.pop();
}
})
return h.heap.map(a => a.key);
};
时间复杂度 空间复杂度分析
因其中有forEach且堆里面的上移下移操作都是
Olog(k)，所以****时间复杂度****为Onlog(k)因堆大小由数组K决定，所以****空间复杂度****为
O(n)
LeetCode: 23. 合并K个升序链表
题目描述
解题思路
解题步骤
Code
class MinHeap {
constructor() { // 声明在构造函数
this.heap = []; // 建立一个空数组用来存放堆
}
swap(i1, i2){ // 8. 封装一个交换函数
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
getParentIndex(i){ // 4. 封装获取 当前节点的父节点 的方法
return Math.floor( (i - 1) / 2 ); // Math.floor取商的操作
}
getLeftIndex(i){ // 14. 封装获取 当前节点的左子节点 的方法
return 2 * i + 1;
}
getRightIndex(i){ // 15. 封装获取 当前节点的右子节点 的方法
return 2 * i + 2;
}
shiftUp(index){ // 3. 封装上移操作的方法
if(index === 0){return}; // 10. 若上移至堆顶则停止上移
const parentIndex = this.getParentIndex(index); // 5. 获取父节点
if(this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val){ // 6. 若父节点的值大于该节点的值则需要交换
this.swap(parentIndex, index); // 7. 封装一个交换函数
this.shiftUp(parentIndex); // 9. 交换之后继续执行上移操作
}
}
shiftDown(index){ // 13. 封装下移操作的方法 因要与子节点交换，故封装两个获取子节点的方法
const leftIndex = this.getLeftIndex(index); // 16. 获取左侧子节点
const rightIndex = this.getRightIndex(index); // 17. 获取右侧子节点
if(this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val){ // 18. 若左子节点值小于当前节点的值则交换
this.swap(leftIndex, index);
this.shiftDown(leftIndex); // 19. 交换之后继续执行下移操作
}
// 20. 右侧子节点相同的操作
if(this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val){ // 18. 若右子节点值小于当前节点的值则交换
this.swap(rightIndex, index);
this.shiftDown(rightIndex); // 19. 交换之后继续执行下移操作
}
}
insert(value) { // 1. 封装插入堆方法
this.heap.push(value);
this.shiftUp(this.heap.length - 1); // 2. 封装一个上移操作的函数, 传入最后一个元素
}
pop(){ // 11. 封装删除堆的方法
if(this.size() === 1) return this.heap.shift();
const top = this.heap[0];
this.heap[0] = this.heap.pop(); // 将最后一个元素删除并替换堆顶元素
this.shiftDown(0); // 12. 封装一个下移操作的方法
return top;
}
peek(){ // 21. 获取堆顶元素
return this.heap[0];
}
size(){ // 31. 获取堆的大小
return this.heap.length;
}
}
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
const res = new ListNode(0); // 1. 新建一个链表
let p = res; // 6. 声明一个指针
const h = new MinHeap(); // 3. 实例化最小堆
lists.forEach( l => {
if(l) h.insert(l); // 4. 将链表的头部插入堆中
})
while(h.size()){ // 5. 当堆不为空循环
const n = h.pop();
p.next = n; // 7. 将最小堆的堆头拿出并放入链表中
p = p.next; // 8. 指针开始往下移动
if(n.next) h.insert(n.next); // 因为最小的已被消耗，接下来要将下一个插入堆
}
return res.next; // 2. 最终返回的是res的next
};
时间复杂度 空间复杂度分析
因其中有forEach且堆里面的上移下移操作都是
Olog(k)，所以时间复杂度为Onlog(k)因堆大小为K，所以空间复杂度为
O(k)
总结
