优先级队列（头条面试题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//实现一个优先级队列，此队列具有enqueue（val，prior）和dequeue（）两种操作，分别代表入队和出队。
//其中enqueue（val，prior）第一个参数val为为值，第二个参数prior为优先级（prior越大，优先级越高），优先级越高越先出队
//dequeue（）出队操作，每调用一次从队列中找到一个优先级最高的元素出队，并返回此元素的值（val）
//要求：在O（logn）时间复杂度内完成两种操作
class PriorityQueue {
constructor() {
//数组，入队的元素保存在这里，
//每进行一次入队或出队操作，都需重新调整数组为大顶堆
this.arr = [];
}
//入队
enqueue(val, prior) {
this.arr.push({
val: val,
prior: prior
});
let cur = this.arr.length - 1;
let temp = this.arr[cur];
//对刚入队的那个元素实施上浮操作，即重新调整数组为大顶堆
for(let i = Math.floor((cur - 1) / 2); i >= 0; i = Math.floor((i - 1) / 2)) {
if(temp.prior > this.arr[i].prior) {
this.arr[cur] = this.arr[i];
cur = i;
} else break;
}
this.arr[cur] = temp;
}
//出队
dequeue() {
if(this.arr.length === 0) throw new Error("队列为空，不能出队");
//大顶堆保证了第一个元素的优先级永远最高，是要出队的元素
//将第一个元素的值缓存，以便返回
let res = this.arr[0].val;
//用队尾元素元素覆盖第一个元素
this.arr[0] = this.arr[this.arr.length - 1];
//将队列长度-1
this.arr.length -= 1;
//重新调整队列为大顶堆
let cur = 0,
len = this.arr.length;
let temp = this.arr[0];
for(let i = 2 * cur + 1; i < len; i = 2 * cur + 1) {
if(i + 1 < len && this.arr[i].prior < this.arr[i + 1].prior)
i++;
if(temp.prior < this.arr[i].prior) {
this.arr[cur] = this.arr[i];
cur = i;
} else break;
}
this.arr[cur] = temp;
//返回结果
return res;
}
}
let p = new PriorityQueue();
p.enqueue(5, 6);
p.enqueue(2, 100);
p.enqueue(90, 1);
console.log(p.dequeue());//2
console.log(p.dequeue());//5
console.log(p.dequeue());//90