2020年秋天还没到，互联网公司便按捺不住招贤纳士的步伐了，开始启动秋季招聘的提前批工作。最近有读者昨天刚参加完字节跳动的提前批一面，与我交流时聊了他的面试经历，因为之前我在春招时也面试过字节跳动。

在整个的面试流程中，字节跳动至少会有 3 轮技术面，每一轮面试都会考算法。 像这位读者的面试中，面试官让他写优先队列的实现算法并且讲解思路，他回答了4种实现：无序数组、有序数组、无序链表和有序链表的实现，当时面试官夸他讲得很全，结果一面过了。 今天结合读者的面试经历，我讲一讲优先队列的四种实现方法。

优先队列

优先队列，与堆栈和队列一样，都是元素的集合。在删除操作上，栈是先进后出的数据结构，删除最近添加的元素；普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除；在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的特性。

优先级队列的主要操作是insert，delMax（删除最大值） 和 isEmpty（判断是否为空）。

优先级队列有很多应用，例如：

• AI中的A *搜索算法

• 使用Huffman编码进行数据压缩

• 事件-驱动模拟（Event-driven simulation）

无序数组实现优先队列

优先级队列类

构造一个最大优先级队列，其中具有最大值的元素具有最高优先级。Key必须扩展Comparable接口。这是因为我们要在优先级队列中的元素之间进行比较，而不是在优先级队列对象之间进行比较。

优先级队列类：Key[] pq是通用类型的数组 ，N表示该数组中的元素数。

public class UnorderedArrayMaxPQ<Key extends Comparable<Key>> { private Key[] pq; private int N; public UnorderedArrayMaxPQ(int capacity) {          pq = (Key[]) new Comparable[capacity];          N = 0; } } 

操作函数

insert（）：将元素插入数组的末尾

delMax()：每次查找最大元素数时，都需要扫描所有元素。删除最大元素的技巧是，将最大元素与数组中的最后一个元素交换，然后将其删除。

isEmpty()：判断队列是否为空

//将元素插入数组的末尾 public void insert(Key item) { pq[N++] = item; } //删除（并返回）最大项 public Key delMax() { int max = 0; for (int i = 1; i < N; i++) if (less(max, i)) max = i; swap(max, N-1); return pq[--N]; } //队列是否为空？ public boolean isEmpty() { return N == 0; } 

有序数组实现优先队列

优先级队列类

public class OrderedArrayMaxPQ<Key extends Comparable<Key>> { private Key[] pq; private int N; public OrderedArrayMaxPQ(int capacity) {         pq = (Key[]) (new Comparable[capacity]);         N = 0; } } 

操作函数

insert（）：将元素插入到已排序位置的数组中，维护排序的数组。

delMax()：max元素将始终位于末尾，将其删除。

isEmpty()：判断队列是否为空。

//将元素插入到已排序位置的数组中 public void insert（Key item）{ int i = N-1; //只要新元素小于pq [i]，就向右移动 while (i >= 0 && less(item, pq[i])) {         pq[i+1] = pq[i];         i--; }     pq[i+1] = item;     N++; } //删除（并返回）最大项 public key delMax（）{return pq [-N]; } //队列是否为空？ public boolean isEmpty（）{return N == 0; } 

无序链表实现优先队列

链表节点的实现

private class Node {      Key item;      Node next; } 

操作函数

insert（）：采用头插法将元素插入链表。

delMax()：每次查找链表的最大元素数时，然后将其删除。

isEmpty()：判断链表是否为空。

public boolean isEmpty() { return N==0;} public void Insert(Key v) {    Node Item=new Node();    Item.item=v;    Item.next=first;    first=Item;    N++; } public Key delMax() {     Node Item=new Node();     Item.next=first;         Node maxItem=first;     Node maxItemPrev=Item; while(Item.next.next!=null) { if(less(maxItem.item,Item.next.next.item)) {           maxItem=Item.next.next;           maxItemPrev=Item.next; }       Item=Item.next; }         Key max=maxItem.item;     maxItemPrev.next=maxItem.next; if(first==maxItem) first=maxItem.next;     maxItem=null;     N--; return max; } 

完整代码

public class UnOrderedListMaxPQ<Key extends Comparable<Key>> { private class Node {         Key item;         Node next; } //无序链表实现优先队列大堆 private Node first; private int N=0; public boolean isEmpty() { return N==0;} public int size() { return N;} public void Insert(Key v) {        Node Item=new Node();        Item.item=v;        Item.next=first;        first=Item;        N++; } public Key delMax() {         Node Item=new Node();         Item.next=first;                 Node maxItem=first;         Node maxItemPrev=Item; while(Item.next.next!=null) { if(less(maxItem.item,Item.next.next.item)) {               maxItem=Item.next.next;               maxItemPrev=Item.next; }           Item=Item.next; }                 Key max=maxItem.item;         maxItemPrev.next=maxItem.next; if(first==maxItem) first=maxItem.next;         maxItem=null;         N--; return max; } public static void main(String[] args) {         E2d4d3v3 pq=new E2d4d3v3();         pq.Insert(1);         pq.Insert(3);         StdOut.println(pq.delMax());         pq.Insert(2);         StdOut.println(pq.delMax());         StdOut.println(pq.delMax()); } } } 

有序链表实现优先队列

链表节点的实现

 private class Node {         Key item;         Node next; } 

操作函数

insert（）：将元素插入链表，并保持链表的顺序。

delMax()：链表的最大元素始终位于链表头部，每次删除链表的最大元素时，将链表头部的元素删除。

isEmpty()：判断链表是否为空。

public boolean isEmpty() { return N==0;} public int size() { return N;} public void Insert(Key v) {    Node newItem=new Node();    newItem.item=v;       Node Item=new Node();    Item.next=first; while(Item.next!=null && less(newItem.item,Item.next.item))          Item=Item.next;        newItem.next=Item.next;     Item.next=newItem; //0节点增加新节点 或 新节点为最大时修改first if(first==null || first==newItem.next)   first=newItem;     N++; } public Key delMax() {    Node maxItem=first;    first=first.next;    Key max=maxItem.item;    N--; return max; } 

完整代码

public class OrderedListMaxPQ<Key extends Comparable<Key>> { private class Node {         Key item;         Node next; } //有序链表实现优先队列大堆,first存储最大元素 private Node first; private int N=0; public boolean isEmpty() { return N==0;} public int size() { return N;} public void Insert(Key v) {        Node newItem=new Node();        newItem.item=v;               Node Item=new Node();        Item.next=first; while(Item.next!=null && less(newItem.item,Item.next.item))              Item=Item.next;                newItem.next=Item.next;         Item.next=newItem; //0节点增加新节点 或 新节点为最大时修改first if(first==null || first==newItem.next)   first=newItem;         N++; } public Key delMax() {        Node maxItem=first;        first=first.next;        Key max=maxItem.item;        N--; return max; } public static void main(String[] args) {         OrderedListMaxPQ pq=new OrderedListMaxPQ();         pq.Insert(1);         pq.Insert(3);         StdOut.println(pq.delMax());         pq.Insert(2);         StdOut.println(pq.delMax());         StdOut.println(pq.delMax()); } } 

总结

咱们玩归玩，闹归闹，别拿面试开玩笑！吐槽字节跳动的“凡面试必算法”的同时，也要明白为啥很多公司要考这么多算法？其实核心是看候选人是不是足够聪明，很多公司招聘工程师的必要条件就是聪明。

优先队列的实现本身不难，但是像读者这样，优先队列的四种实现方式全部讲出来的面试者很少。读者顺利通过了一面，接下的面试还在继续，祝愿这位读者能顺利拿到字节offer！

作者：AlexanderChen
链接：https://juejin.im/post/5eea2654f265da02c94e0f04
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

文章持续更新，可以微信搜索「 云璈公子 」阅读，回复【资料】【面试】【简历】有我准备的一线大厂面试资料和简历模板，同时我的GitHub https://github.com/1170300826/JavaInterview 有互联网一线大厂面试指南。