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

来源：算法面试题

优先级队列，不同于先进先出队列，其对每一个元素指定了优先级，一般情况下，出队时，优先级越高的元素越先出队。在面试过程中，优先级队列是面试官喜欢问的一个考点。

问题

(头条一面面试题)

实现一个优先级队列，此队列具有enqueue（val，prior）和dequeue（）两种操作，分别代表入队和出队。

其中enqueue（val，prior）第一个参数val为值，第二个参数prior为优先级（prior越大，优先级越高），优先级越高越先出队

dequeue（）出队操作，每调用一次从队列中找到一个优先级最高的元素出队，并返回此元素的值（val）

要求：在O（logn）时间复杂度内完成两种操作

---

思考三分钟再往下看效果更佳哦

。。。

。。。

。。。

。。。

。。。

思路

此题是一道较难的题，难点在于要求两种操作均在O（logn）时间复杂度内完成。

此题的关键点在于是否能够想到二叉堆（普及一下二叉堆，二叉堆将数组维护成了逻辑上的完全二叉树，但其本质上（存储结构）是数组，这一点要注意），如果能想到这一点那么这道面试题就成功一半了，因为利用二叉堆我们就可以在O（logn）复杂度内实现入队出队操作（前面介绍了通过链表的方式可以使入队操作在O（1）时间内完成，而通过二叉堆需要O（logn）完成，表面上似乎复杂度升高了，但是我们将入队和出队操作结合起来看，那么整体效率还是二叉堆方式效率更高）。

那么二叉堆为何如此神通广大呢？其实，熟悉堆排序的朋友对二叉堆应该不会陌生，下面我就对二叉堆是如何降低复杂度做个介绍（以大顶堆为例）。

首先，在入队时，先将元素放在最后一个位置上，然后比较此元素与其父元素优先级的大小，若此元素优先级较大，则需上浮，直到根节点为止（注：二叉堆的存储结构是一个数组，下面的图左边是数组，即二叉堆的实际存储结构，右边是此数组对应的完全二叉树，方便讲解上浮下沉操作）。

下面以图的方式说明具体上浮过程（假设分别入队了1，2，3，4，数字代表优先级，构建的是大顶堆）：

大家不难发现入队时上浮元素的目的是将数组调整成大顶堆，方便之后的入队出队操作。

然后是出队操作，假设我们在上述的4入队之后进行了一次出队操作，那么优先级最高的4（即数组的第一个元素）将被移出队列。但是，具体的移除操作并不是将第一个元素4删除这么简单，我们需要重新调整数组为大顶堆，具体分为三步：

第一步：将第一个元素与最后一个元素交换（目的：这样就可以在不影响其他元素的情况下把元素4删除了，方便后续重新调整为大顶堆，若不交换直接删除4，则后续重新调整为大顶堆时较麻烦）；

第二步：现在可以将4删除了；

第三步：重新调整数组为大顶堆，注：此时需要对根节点（数组中的第一个元素）实施下沉操作，一直下沉到叶节点为止，在下沉过程中，根节点要与左右孩子中较大的一个交换，这样才能调整为大顶堆；

如图，大顶堆又形成了。接下来，就可以继续对队列实施入队出队操作了。我们发现入队出队的时间都用在了将数组调整成大顶堆上了，其时间复杂度为二叉堆的高度，即O（logn）。

代码实现

下面是作者用JavaScript实现的代码，仅供参考！（建议大家自己动手实现一

遍）

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


温馨提示：可左右滑动

复制代码请前往https://blog.csdn.net/Great_Eagle/article/details/83117236

·END·

 近期热文：

看完，赶紧点个“好看”鸭

点鸭点鸭

↓↓↓↓