【JS】优先队列和二叉堆
优先队列和二叉堆
cvSoldier发布于 今天 12:00
起因是一场周赛的题目 1705. 吃苹果的最大数目
描述中的第四天到第七天吃的都是第四天的苹果,我以为是记录当前剩余苹果的贪心,实际应该是
- 第四天,吃掉一个第四天长出的苹果。
- 第五天,第四天的四个苹果保质三天,第五天的两个苹果保质两天,吃掉一个第五天的苹果
- 第六天,第四天的四个苹果保质两天,第五天的一个苹果保质一天,吃掉一个第五天的苹果
- 第七天,第四天的四个苹果保质一天,吃掉一个第四天苹果
- 第八天,第四天的三个苹果保质零天,没的吃。
做题
要优先吃快要坏掉的苹果,分为三步:
var eatenApples = function(apples, days) {let aLen = apples.length
let eat = 0
let queue = [] // 按照好坏程度排序的苹果队列
let i = 0 // 当前是第几天
// todo
// 1、把今天的苹果收起来
// 2、把坏掉的苹果扔掉
// 3、吃一个
return eat
};
1、收苹果
// 收苹果时需要把当天的苹果放入合适位置// 以保证 queue 是按照从坏到好的顺序
if(i < aLen && apples[i]) {
let j = queue.length - 1
while(j >= 0 && ((i + days[i]) < (queue[j] + days[queue[j]]))) {
// queue不为空 且 当前天的苹果的保质期 < queue倒序中的苹果的保质期
queue[j + 1] = queue[j]
j--
}
queue[j + 1] = i
}
2、扔坏苹果
while(queue.length > 0 &&
(apples[queue[0]] <= 0 || i >= (queue[0] + days[queue[0]]))
// 第一坏的位置没苹果了 或者 第一坏的位置已经过保质期了
) queue.shift()
3、吃
if(queue.length > 0) {apples[queue[0]]--
eat++
}
已经可以过了,但是只击败了56%,原因在于我们优先队列的实现方式是简单数组,每次插入和 shift() 的时候都是 O(n)
的复杂度,接下来就是使用二叉堆来实现一个优先队列。
二叉堆
二叉堆本质是完全二叉树,分为最大堆和最小堆,最大堆就是任意一个父节点,都大于他的子节点的值,最小堆同理,任意一个父节点都小于他的子节点的值。
二叉堆的根节点叫做堆顶,最大堆的根节点是堆的最大元素,最小堆的根节点是堆的最小元素。
二叉堆的操作包括:插入节点,删除节点,构建二叉堆,这三种操作又都是基于节点的上浮和下沉
(图为插入节点和删除节点示意)
下面使用数组来简单实现一个最小二叉堆
function BinaryHeap() {this.list = []
}
BinaryHeap.prototype = {
push(data) {
this.list.push(data)
this._moveUp()
},
pop() {
const data = this.list[0]
this.list[0] = this.list[this.list.length - 1]
this.list.pop()
this._moveDown(0)
return data
},
// 节点上浮
_moveUp() {
let childIndex = this.list.length - 1
let parentIndex = (childIndex - 1) >>> 1
let temp = this.list[childIndex]
while(childIndex > 0 && temp < this.list[parentIndex]) {
this.list[childIndex] = this.list[parentIndex]
childIndex = parentIndex
parentIndex = (parentIndex - 1) >>> 1
}
this.list[childIndex] = temp
},
// 节点下沉
_moveDown(index) {
let parent = index
let temp = this.list[parent]
let child = 2 * parent + 1
while(child < this.list.length) {
if(child < this.list.length - 1 && this.list[child + 1] < this.list[child]) {
// 如果有两个子节点, 将父节点下沉到更小的节点的位置
child++
}
if(this.list[child] < temp) {
this.list[parent] = this.list[child]
parent = child
child = 2 * parent + 1
} else {
break
}
}
this.list[parent] = temp
}
}
二叉堆的push
和pop
都是 logn 的复杂度,类比二分查找,大家都是 logn,能不能用二分代替嘞,不能。
因为二叉堆的 logn 是 查 + 替换, 二分查找的 logn 只有查,替换是 n,所以不能。
应用
下面使用二叉堆来改写代码,只需要把我们实现的二叉堆中是否上浮和下沉的对比条件修改一下,重复代码就不占篇幅了,大概代码如下
function BinaryHeap(compareArr) {this.list = []
this.compareArr = compareArr
}
BinaryHeap.prototype = {
lessThan(index1, index2) {
return (index1 + this.compareArr[index1]) < (index2 + this.compareArr[index2])
},
first() {
return this.list[0]
},
length() {
return this.list.length
},
push(data) {
// ...
},
pop() {
// ...
},
_moveUp() {
// ...
while(childIndex > 0 && this.lessThan(temp, this.list[parentIndex])) {
// ...
}
// ...
},
_moveDown(index) {
// ...
while(child < this.list.length) {
if(child < this.list.length - 1 && this.lessThan(this.list[child + 1],this.list[child])) {
child++
}
if(this.lessThan(this.list[child], temp)) {
// ...
} else {
break
}
}
this.list[parent] = temp
}
}
var eatenApples = function(apples, days) {
let aLen = apples.length
let eat = 0
let queue = new BinaryHeap(days)
let i = 0
while(i < aLen || queue.length > 0) {
if(i < aLen && apples[i]) {
queue.push(i)
}
while(
queue.length() > 0 &&
(apples[queue.first()] <= 0 || (queue.first() + days[queue.first()]) <= i)
) queue.pop()
if(queue.length() > 0) {
apples[queue.first()]--
eat++
}
i++
}
return eat
};
二叉堆版本的代码和最初的速度对比
图中序号2和3是二叉堆版本和线性数组的时间对比,也从击败56%提升到92%
序号1则是速度排在最前面的答案的重新提交,但是有一个测试用例不通过,可能是补充用例之前的提交。
最后的代码看起来确实很长,但是把二叉堆单拎出来,阅读起来可能更清晰一点。
javascriptleetcode堆
阅读 36发布于 今天 12:00
本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议
cvSoldier
<a href="https://segmentfault.com/u/cvsoldier">原地tp</a>
98 声望
5 粉丝
cvSoldier
<a href="https://segmentfault.com/u/cvsoldier">原地tp</a>
98 声望
5 粉丝
宣传栏
目录
起因是一场周赛的题目 1705. 吃苹果的最大数目
描述中的第四天到第七天吃的都是第四天的苹果,我以为是记录当前剩余苹果的贪心,实际应该是
- 第四天,吃掉一个第四天长出的苹果。
- 第五天,第四天的四个苹果保质三天,第五天的两个苹果保质两天,吃掉一个第五天的苹果
- 第六天,第四天的四个苹果保质两天,第五天的一个苹果保质一天,吃掉一个第五天的苹果
- 第七天,第四天的四个苹果保质一天,吃掉一个第四天苹果
- 第八天,第四天的三个苹果保质零天,没的吃。
做题
要优先吃快要坏掉的苹果,分为三步:
var eatenApples = function(apples, days) {let aLen = apples.length
let eat = 0
let queue = [] // 按照好坏程度排序的苹果队列
let i = 0 // 当前是第几天
// todo
// 1、把今天的苹果收起来
// 2、把坏掉的苹果扔掉
// 3、吃一个
return eat
};
1、收苹果
// 收苹果时需要把当天的苹果放入合适位置// 以保证 queue 是按照从坏到好的顺序
if(i < aLen && apples[i]) {
let j = queue.length - 1
while(j >= 0 && ((i + days[i]) < (queue[j] + days[queue[j]]))) {
// queue不为空 且 当前天的苹果的保质期 < queue倒序中的苹果的保质期
queue[j + 1] = queue[j]
j--
}
queue[j + 1] = i
}
2、扔坏苹果
while(queue.length > 0 &&
(apples[queue[0]] <= 0 || i >= (queue[0] + days[queue[0]]))
// 第一坏的位置没苹果了 或者 第一坏的位置已经过保质期了
) queue.shift()
3、吃
if(queue.length > 0) {apples[queue[0]]--
eat++
}
已经可以过了,但是只击败了56%,原因在于我们优先队列的实现方式是简单数组,每次插入和 shift() 的时候都是 O(n)
的复杂度,接下来就是使用二叉堆来实现一个优先队列。
二叉堆
二叉堆本质是完全二叉树,分为最大堆和最小堆,最大堆就是任意一个父节点,都大于他的子节点的值,最小堆同理,任意一个父节点都小于他的子节点的值。
二叉堆的根节点叫做堆顶,最大堆的根节点是堆的最大元素,最小堆的根节点是堆的最小元素。
二叉堆的操作包括:插入节点,删除节点,构建二叉堆,这三种操作又都是基于节点的上浮和下沉
(图为插入节点和删除节点示意)
下面使用数组来简单实现一个最小二叉堆
function BinaryHeap() {this.list = []
}
BinaryHeap.prototype = {
push(data) {
this.list.push(data)
this._moveUp()
},
pop() {
const data = this.list[0]
this.list[0] = this.list[this.list.length - 1]
this.list.pop()
this._moveDown(0)
return data
},
// 节点上浮
_moveUp() {
let childIndex = this.list.length - 1
let parentIndex = (childIndex - 1) >>> 1
let temp = this.list[childIndex]
while(childIndex > 0 && temp < this.list[parentIndex]) {
this.list[childIndex] = this.list[parentIndex]
childIndex = parentIndex
parentIndex = (parentIndex - 1) >>> 1
}
this.list[childIndex] = temp
},
// 节点下沉
_moveDown(index) {
let parent = index
let temp = this.list[parent]
let child = 2 * parent + 1
while(child < this.list.length) {
if(child < this.list.length - 1 && this.list[child + 1] < this.list[child]) {
// 如果有两个子节点, 将父节点下沉到更小的节点的位置
child++
}
if(this.list[child] < temp) {
this.list[parent] = this.list[child]
parent = child
child = 2 * parent + 1
} else {
break
}
}
this.list[parent] = temp
}
}
二叉堆的push
和pop
都是 logn 的复杂度,类比二分查找,大家都是 logn,能不能用二分代替嘞,不能。
因为二叉堆的 logn 是 查 + 替换, 二分查找的 logn 只有查,替换是 n,所以不能。
应用
下面使用二叉堆来改写代码,只需要把我们实现的二叉堆中是否上浮和下沉的对比条件修改一下,重复代码就不占篇幅了,大概代码如下
function BinaryHeap(compareArr) {this.list = []
this.compareArr = compareArr
}
BinaryHeap.prototype = {
lessThan(index1, index2) {
return (index1 + this.compareArr[index1]) < (index2 + this.compareArr[index2])
},
first() {
return this.list[0]
},
length() {
return this.list.length
},
push(data) {
// ...
},
pop() {
// ...
},
_moveUp() {
// ...
while(childIndex > 0 && this.lessThan(temp, this.list[parentIndex])) {
// ...
}
// ...
},
_moveDown(index) {
// ...
while(child < this.list.length) {
if(child < this.list.length - 1 && this.lessThan(this.list[child + 1],this.list[child])) {
child++
}
if(this.lessThan(this.list[child], temp)) {
// ...
} else {
break
}
}
this.list[parent] = temp
}
}
var eatenApples = function(apples, days) {
let aLen = apples.length
let eat = 0
let queue = new BinaryHeap(days)
let i = 0
while(i < aLen || queue.length > 0) {
if(i < aLen && apples[i]) {
queue.push(i)
}
while(
queue.length() > 0 &&
(apples[queue.first()] <= 0 || (queue.first() + days[queue.first()]) <= i)
) queue.pop()
if(queue.length() > 0) {
apples[queue.first()]--
eat++
}
i++
}
return eat
};
二叉堆版本的代码和最初的速度对比
图中序号2和3是二叉堆版本和线性数组的时间对比,也从击败56%提升到92%
序号1则是速度排在最前面的答案的重新提交,但是有一个测试用例不通过,可能是补充用例之前的提交。
最后的代码看起来确实很长,但是把二叉堆单拎出来,阅读起来可能更清晰一点。
以上是 【JS】优先队列和二叉堆 的全部内容, 来源链接: utcz.com/a/111723.html
得票时间