注释 plus
堆是动静求极值的数据结构,所以当遇到须要一直取极值的时候,就能够思考用堆了
舒适提醒,倡议每一道题都本人 new 一个堆,这样能力发现堆之美,其实就是不会再次遇到 topK 的时候只能用冒泡来做。
行文至此也该完结了,如果有 10 个关注,那就更新一下下一 part, dp 或者树吧, thx。
二叉堆的创立
剖析 — 小顶堆
- 这里是一个小顶堆,特点就是根节点的值比子节点的值都小,通常用作经典的前 K 大
-
次要有两个办法,
- 一个是回升,这里次要用作构建堆的时候,整顿堆用的
- 一个是下沉,这里次要用于弹出堆顶元素后,置换了堆顶值之后应用的,这里用到 this.data[0],是因为这个办法个别是构建残缺的堆之后,才会应用
- 其余的办法不是不能够,只是为了保障灵活性,临时就先做个简易版,前面再思考,因为办法越多,其实兼容性就越差了
class MinHeap {
constructor(len) {
this.data = [];
this.data[0] = len; // 第一个节点用来寄存堆的大小 -- 某些特定环境比拟好用
}
// 下浮
down(index) {
const size = this.data[0];
while (index << 1 <= size) {
let child = index << 1;
if (child !== size && this.data[child] > this.data[child + 1]) {
child += 1; //如果右节点更小,就右节点作为下一个接盘的节点
}
if (this.data[index] > this.data[child]) {
// 替换一下
[this.data[index], this.data[child]] = [
this.data[child],
this.data[index],
];
index = child;
} else {
// 只有其中一次生效了,那么就没必要持续往下查找了
break;
}
}
}
// 都是从最底层开始算的
upper() {
// 这里不必 this.data[0] 是因为以后构建的堆可能还没达到堆的最大值,所以不能应用
let index = this.data.length - 1;
while (index >> 1 > 0) {
let father = index >> 1;
if (this.data[index] < this.data[father]) {
// 子节点比父节点要小,则网上走
[this.data[index], this.data[father]] = [
this.data[father],
this.data[index],
];
index = father;
} else {
break;
}
}
}
}
剖析 — 大顶堆
- 绝对于初始版的小顶堆,这一版的大顶堆增加了两个办法, pop 和 add
- add 办法能够写在应用堆的地位,然而为了让它和堆的第一个值匹配,所以写在了类办法外面,不便对 size 的增加
- pop 是为了取出堆顶元素,
堆是为了解决动静取极值
而存在的数据结构,所以必然要取出整顿的过程。
class MaxHeap {
constructor() {
this.data = [];
this.data[0] = 0; // 第一个值是以后堆的size
}
down(index) {
const len = this.data.length; // 是下标极限
while (index << 1 < len) {
let child = index << 1;
if (child !== len && this.data[child + 1] > this.data[child]) {
child++;
}
if (this.data[child] > this.data[index]) {
[this.data[child], this.data[index]] = [
this.data[index],
this.data[child],
];
index = child;
} else {
break;
}
}
}
upper() {
let index = this.data[0]; // 最大下标
while (index >> 1 > 0) {
const father = index >> 1;
if (this.data[index] > this.data[father]) {
[this.data[father], this.data[index]] = [
this.data[index],
this.data[father],
];
index = father;
} else {
break;
}
}
}
add(value) {
// 先加在最开端
this.data.push(value);
this.data[0]++; // size 也加一下
this.upper(); // 整顿一下
}
// 弹出堆顶元素
pop() {
const last = this.data[0];
[this.data[1], this.data[last]] = [this.data[last], this.data[1]]; //替换堆顶和堆尾的值
const ret = this.data.pop();
this.data[0]--;
this.down(1); // 整顿
return ret;
}
}
215. 数组中的第K个最大元素
剖析
- 这是一道炒鸡经典的题,能够用冒泡,快排,其中最经典的办法,莫过于小顶堆求值 — 作为教材根本的题目
- 这里求第 K 大,那么就是要保护一个 K 大的小顶堆,而后堆顶就是第 K 大
- 而后遍历数组 nums,先初始化一个 K 大的小顶堆,而后剩下的值就和堆顶比拟;
- 只有是值大过堆顶值的,那么间接把堆顶值替换掉,但这时,堆顶值就不肯定是小顶堆中的最小值了,所以须要向下 down 整顿一下小顶堆
- 遍历完结后就失去一个小顶堆了,而后间接去堆顶元素就是第 K 大了;
- 工夫复杂度: {O(N*L) — 其中 N 是数组大小, L 是二叉堆的层高,L其实相对来说比拟小,所以复杂度能够说靠近线性
- 空间复杂度: O(M) — 其中 M 是就是 K 值,因为要保护一个 K 大堆
// 215. 数组中的第K个最大元素
// MinHeap 就是下面的那个类
var findKthLargest = function (nums, k) {
// 创立一个 K 大的小顶堆
const minHeap = new MinHeap(k);
const len = nums.length;
for (let i = 0; i < len; i++) {
if (i < k) {
// 初始化堆
minHeap.data.push(nums[i]);
minHeap.upper();
} else {
// 这个时候开始思考是否要压到小顶堆中了
// 因为保护的是一个 k 大的小顶堆,而目标是求第 k 大,所以只须要判断前面的值是否大于小顶堆的堆顶值,即可知道是否须要取代
if (nums[i] > minHeap.data[1]) {
minHeap.data[1] = nums[i];
minHeap.down(1);
}
}
}
return minHeap.data[1]
};
参考视频:传送门
1046. 最初一块石头的分量
剖析 — 大顶堆
- 依照题目曾经,须要取出一组数组中的最大值和次大值,进行肯定运算后,会将计算值返回给数组,而后循环操作,直到数组长度最大为 1 时完结
- 所以就是动静取极值,能够思考用堆来解决
- 定义一个办法 pop,每次获取堆顶元素,并将大顶堆整顿好,定义方法 add 为为堆退出元素
- 这样每一次取出两个元素,返回 1 或 0 个元素,始终到堆元素小于 2 时完结,返回堆中的元素或 0
- 空间复杂度就是保护堆,所以是 O(N), 工夫复杂度 O(NlogN)
// 1046. 最初一块石头的分量
var lastStoneWeight = function (stones) {
// 保护一个大顶堆
const heap = new MaxHeap();
for (let i = 0; i < stones.length; i++) {
heap.add(stones[i]);
}
while (heap.data[0] > 1) {
// 1. 每次取出两个最大值
const first = heap.pop();
const second = heap.pop();
// 2. 相减,再放回去
const temp = first - second;
if (temp) {
heap.add(temp);
}
}
return heap.data[0] ? heap.data[1]:0
};
class MaxHeap {
constructor() {
this.data = [];
this.data[0] = 0; // 第一个值是以后堆的size
}
down(index) {
const len = this.data.length; // 是下标极限
while (index << 1 < len) {
let child = index << 1;
if (child !== len && this.data[child + 1] > this.data[child]) {
child++;
}
if (this.data[child] > this.data[index]) {
[this.data[child], this.data[index]] = [
this.data[index],
this.data[child],
];
index = child;
} else {
break;
}
}
}
upper() {
let index = this.data[0]; // 最大下标
while (index >> 1 > 0) {
const father = index >> 1;
if (this.data[index] > this.data[father]) {
[this.data[father], this.data[index]] = [
this.data[index],
this.data[father],
];
index = father;
} else {
break;
}
}
}
add(value) {
// 先加在最开端
this.data.push(value);
this.data[0]++; // size 也加一下
this.upper(); // 整顿一下
}
// 弹出堆顶元素
pop() {
const last = this.data[0];
[this.data[1], this.data[last]] = [
this.data[last],
this.data[1],
] //替换堆顶和堆尾的值
const ret = this.data.pop();
this.data[0]--;
this.down(1); // 整顿
return ret
}
}
23. 合并K个升序链表
剖析 — 堆
- 这里次要是把链表当成是堆的一个元素,以链表头的值作为小顶堆创立的基点
- 这里要求失去是 K 个升序链表合并链表,我每次都获取 K 个链表中的最小值,而后放到我本人的链表中,最初失去的就是一个合并完的升序链表了
- 空间复杂度就是保护堆,所以是 O(N∗M), 其中 N 是 lists 的长度, M 是 链表的均匀长度
- 工夫复杂度: 取出值合并到新链表 — O(N∗M)
// 23. 合并K个升序链表
/** * @剖析 * 1. 以链表的表头值作为判断元素,创立小顶堆 */
var mergeKLists = function(lists) {
let emptyNode = new ListNode() // 本人创立一个
// 构建一个堆
const minHeap = new MinHeap()
for (let i = 0; i < lists.length; i++) {
const head = lists[i];
if(head){
minHeap.add(head)
}
}
let cur = emptyNode;
while(minHeap.data[0]){
cur.next =new ListNode(minHeap.pop())
cur = cur.next
}
return emptyNode.next
};
class MinHeap {
constructor(){
this.data = []
this.data[0] = 0
}
down(index){
const lastIndex = this.data[0]
while(index<<1 <= lastIndex){
let child = index<<1
if(child!== lastIndex && this.data[child+1].val<this.data[child].val){
child++
}
if(this.data[child].val<this.data[index].val){
[this.data[child],this.data[index]] = [this.data[index],this.data[child]]
index = child
}else{
break
}
}
}
upper(){
let index = this.data[0]
while(index>>1 > 0){
let father = index>>1
// 以表头值作为判断根据
if(this.data[father].val>this.data[index].val){
// 替换的是整个链表
[this.data[father],this.data[index]] = [this.data[index],this.data[father]]
index = father
}else{
break
}
}
}
add(head){
// 增加的是一个排好序的链表,
this.data.push(head);
this.data[0]++
this.upper()
}
// 将堆顶链表的头部值取出之后,重新整理
pop(){
const ret = this.data[1].val
this.data[1] = this.data[1].next
if(!this.data[1]){
// 链表为 undefined 了
[this.data[1],this.data[this.data[0]]] = [this.data[this.data[0]],this.data[1]]
this.data.pop()
this.data[0]--
}
this.down(1) //整顿
return ret // 返回的是一个值
}
}
剖析 — 分治
- 多个排序链表很难解决,那么两个排序好的链表合并呢?
- 将两个有序链表合成一个,而后放进 list 持续走,最初合成一个即可
- 用分治,如果超出 2 个链表,就拆分了解决,mergeKLists(arr) 最初失去的也是一个排序好的链表,所以每次能够离开治,而后最初 merge 治;
- 合并两个链表的工夫复杂度 O(N),分治解决 M 个链表的复杂度为 O(logM) 所以 O(NlogM) , 其中 N 是链表的长度, M 是链表的数量
/** * @剖析 * 1. 多个排序链表很难解决,那么两个排序好的链表合并呢? * 2. 将两个有序链表合成一个,而后放进 list 持续走,最初合成一个即可 * 3. 用分治,如果超出 2 个链表,就拆分了解决,mergeKLists(arr) 最初失去的也是一个排序好的链表,所以每次能够离开治,而后最初 merge 治; * 4. 合并两个链表的工夫复杂度 ${O(N)}$,分治解决 M 个链表的复杂度为 ${O(logM)}$ 所以 ${O(NlogM)}$ , 其中 N 是链表的长度, M 是链表的数量 */
var mergeKLists = function(lists) {
const len =lists.length
// return lists.reduce((prev,cur) => mergeTwoList(prev,cur)) // 间接 api 递推即可,然而复杂度更高
// 用分治的形式能够将 N 的复杂度升高到 logN
if(len<1) return null
if(len === 1) return lists[0]
if(len === 2) return mergeTwoList(lists[0],lists[1])
const mid = len>>1
return mergeTwoList(mergeKLists(lists.slice(0,mid)),mergeKLists(lists.slice(mid)))
};
// 合并两个有序链表
function mergeTwoList (list1,list2){
const emptyNode = new ListNode()
let cur =emptyNode
while(list1 && list2){
if(list1.val<list2.val){
cur.next= list1
list1 = list1.next
}else{
cur.next= list2
list2 = list2.next
}
cur = cur.next
cur.next = null
}
if(list1) cur.next = list1
if(list2) cur.next = list2
return emptyNode.next
}
451. 依据字符呈现频率排序
剖析
- 既然是要依照呈现评率进行新组装,所以先遍历一次字符串,用 map 将字符和呈现频率作为一组 item 保存起来 — 工夫空间复杂度都是 O(N)
- 这个时候其实只有依照频率从到到小排列好,而后一一取出重装即可
- 这边是用堆排序,然而item 不再是简略的数字,而是一个数组 [key,value],所以相应的办法微调即可
- 堆排是工夫复杂度:O(NlogN), 最终的空间复杂度是 O(N)
// 451. 依据字符呈现频率排序
var frequencySort = function (s) {
let ret = "";
if (!s) return s;
const map = new Map();
const heap = new MaxHeap();
for (let i = 0; i < s.length; i++) {
const item = s[i];
if (map.has(item)) {
map.set(item, map.get(item) + 1);
} else {
map.set(item, 1);
}
}
// 退出堆中,元素值是 [key,value], 要用 value 来进行比对
for (let item of map.entries()) {
heap.add(item);
}
while (heap.data[0]) {
const item = heap.pop();
ret += item[0].repeat(item[1]);
}
return ret;
};
class MaxHeap {
constructor() {
this.data = [];
this.data[0] = 0;
}
down(index) {
const lastIndex = this.data[0]; //最初一个值的下标值
while (index << 1 <= lastIndex) {
let child = index << 1;
if (
child !== lastIndex &&
this.data[child + 1][1] > this.data[child][1]
) {
child++;
}
if (this.data[child][1] > this.data[index][1]) {
// 留神,item 是数组,所以用第二个值做比对,然而替换的是整个 item
[this.data[child], this.data[index]] = [
this.data[index],
this.data[child],
];
index = child;
} else {
break;
}
}
}
upper() {
let index = this.data[0];
while (index >> 1 > 0) {
const father = index >> 1;
if (this.data[father][1] < this.data[index][1]) {
// 留神,item 是数组,所以用第二个值做比对,然而替换的是整个 item
[this.data[father], this.data[index]] = [
this.data[index],
this.data[father],
];
index = father;
} else {
break;
}
}
}
add(item) {
this.data.push(item);
this.data[0]++;
this.upper();
}
pop() {
[this.data[1], this.data[this.data[0]]] = [
this.data[this.data[0]],
this.data[1],
];
this.data[0]--;
const temp = this.data.pop();
this.down(1)
return temp
}
}
378. 有序矩阵中第 K 小的元素
剖析
- 这里就是 item 为数组的 bottomK, 和失常的 top K 只是多了以数组作为元素的解决
- 应用堆排的时候,只须要整顿函数 down 和 upper 比对的时候弄一下就好了
- 不过有一个区别就是,这个 K 有可能大于二维数组的数组长度 Len(matrix), 所以不能间接创立一个 K 大大顶堆取堆顶,反而要将二维数组所有元素都编入到 Len 大小的小顶堆中,而后再取 K 次
- 这也阐明了 top K 这类题的两种堆解法,要不就是设置 K 大/小 的堆,而后一直用元素去代替,要不设置全副元素的堆,而后弹出 K 次值;
- 工夫/空间复杂度 O(NlogN)
// 378. 有序矩阵中第 K 小的元素
/** * @剖析 -- 第 K 小 * 1. 这里给的排好序的矩阵,那么能够用小顶堆将矩阵中元素转移到小顶堆中,每次从堆顶取值后整顿,取到第 K 个即可 */
var kthSmallest = function(matrix, k) {
const minHeap = new MinHeap()
for(let i = 0;i<matrix.length;i++){
minHeap.add(matrix[i])
}
const ret = []
while(--k){
minHeap.pop()
}
return minHeap.pop()
};
class MinHeap {
constructor(){
this.data = []
this.data[0] = 0
}
down(index){
const lastIndex = this.data[0]
while(index<<1 <= lastIndex){
let child = index << 1
if(child!==lastIndex && this.data[child+1][0]< this.data[child][0]){
child++
}
if(this.data[child][0]< this.data[index][0]){
[this.data[child], this.data[index]] = [this.data[index], this.data[child]]
index = child
}else {
break
}
}
}
upper() {
let index = this.data[0]
while(index >>1 > 0){
let father = index >> 1
if(this.data[father][0]> this.data[index][0]){
[this.data[father], this.data[index]] = [this.data[index], this.data[father]]
index = father
}else {
break
}
}
}
add(item){
this.data.push(item)
this.data[0]++
this.upper()
}
// 这里不是间接弹出 item,而只是弹出堆顶的第一个字母,而后再整顿
pop(){
const temp = this.data[1].shift()
if(!this.data[1].length){
// 数组空了
this.data[1] = this.data[this.data[0]]
this.data.pop()
this.data[0]--
}
this.down(1)
return temp
}
}
const ret = kthSmallest([[1,5,9],[10,11,13],[12,13,15]],8)
console.log(ret)
1054. 间隔相等的条形码
剖析
- 为了保障两两不相等,那得保障数量最多的那个条码必须先排完,避免排完其余就省它自个儿了;
- 所以先用 map 存储所有条码值(key)和数量(value)
- 这个时候就和1046. 最初一块石头的分量很像了;
- 然而还有一点区别,就是每次你取出最大的两块,都只能取走一份进行排列,而后就要把剩下的放回去,保障每一次取两个值都是最大;这就好比,咱们这道题是去磨石头,每次相互之间磨掉一层皮,每一次都要拿最初的石头去磨,而1046. 最初一块石头的分量 是间接两个一砸就完结了;
- map 存储时,工夫复杂度和空间复杂度都是 O(N), N 是长度; 堆排,这个算不进去了,大略也是 O(NlogN) 吧
// 1054. 间隔相等的条形码
var rearrangeBarcodes = function (barcodes) {
// 1. 将条形码的值和数量用 map 存储起来
const map = new Map();
for (let i = 0; i < barcodes.length; i++) {
const item = barcodes[i];
if (map.has(item)) {
map.set(item, map.get(item) + 1);
} else {
map.set(item, 1);
}
}
// 2.创立最大堆,进行堆排
const heap = new MaxHeap();
for (let item of map.entries()) {
heap.add(item); // [key,value]
}
// 3. 每次取出最大的两个 item 进行重写排列
const ret = [];
while (heap.data[0] > 1) {
// 这里是默认是保障存在答案,所以即使最初还有item,那么对应的值也只有1个
// 然而如果条件没有已知,那么就能够依据这个值进行判断是否胜利了
const first = heap.pop();
const second = heap.pop();
// Error:谬误
// while(second[1]--){
// ret.push(first[0])
// ret.push(second[0])
// first[1]--
// }
ret.push(first[0]);
first[1]--;
ret.push(second[0]);
second[1]--;
// 而后就要放回去了
if (first[1]) {
// 如果还有值,放回堆里再来
heap.add(first);
}
if (second[1]) {
// 如果还有值,放回堆里再来
heap.add(second);
}
}
if (heap.data[0]) {
ret.push(heap.pop()[0]);
}
return ret;
};
class MaxHeap {
constructor() {
this.data = [];
this.data[0] = 0;
}
down(index) {
const lastIndex = this.data[0];
while (index << 1 <= lastIndex) {
let child = index << 1;
if (
child !== lastIndex &&
this.data[child + 1][1] > this.data[child][1]
) {
child++;
}
if (this.data[child][1] > this.data[index][1]) {
[this.data[child], this.data[index]] = [
this.data[index],
this.data[child],
];
index = child;
} else {
break;
}
}
}
upper() {
let index = this.data[0];
while (index >> 1 > 0) {
let father = index >> 1;
if (this.data[father][1] < this.data[index][1]) {
[this.data[father], this.data[index]] = [
this.data[index],
this.data[father],
];
index = father;
} else {
break;
}
}
}
add(item) {
this.data.push(item);
this.data[0]++;
this.upper();
}
pop() {
[this.data[1], this.data[this.data[0]]] = [
this.data[this.data[0]],
this.data[1],
];
const item = this.data.pop();
this.data[0]--;
this.down(1);
return item;
}
}
console.log(rearrangeBarcodes([7, 7, 7, 8, 5, 7, 5, 5, 5, 8]));