算法与数据结构系列之[优先队列]

前面我们介绍了队列这种数据结构，不过我们在前面所介绍的队列只是一种普通的队列，即元素先进先出，其实队列还可以分优先级，优先级高的元素先出，比如操作系统的调度，会将优先级高的任务先调度执行，这种队列就叫做优先队列。

那么优先队列底层该如何实现呢？

1.优先队列可以使用普通的线性结构，比如动态数组，入队时的时间复杂度为O(1),出队时需要遍历元素，找到优先级最大的元素出队，时间复杂度为O(n)。

2.使用顺序线性结构，入队时需要按优先级大小排序存储，所以时间复杂度为O(n)，出队时只需要按优先级大小出队即可，时间负责度为O(1)。

3.使用堆这种数据结构，其入队和出队的时间复杂度都为O(logn)。数据量大时，这种使用堆这种数据结构非常高效。

优先队列的java代码实现(这里用最大堆，jdk的优先队列是用最小堆实现的)：

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

   private MaxHeap<E> maxHeap;  //用最大堆实现

   public PriorityQueue(){
       maxHeap = new MaxHeap<>();
   }

   @Override
   public int getSize() {
       return maxHeap.getSize();
   }

   @Override
   public boolean isEmpty() {
       return maxHeap.isEmpty();
   }

   @Override
   public void enqueue(E e) {
       maxHeap.add(e);
   }

   @Override
   public E dequeue() {
       return maxHeap.extractMax();
   }

   @Override
   public E getFront() {
       return maxHeap.findMax();
   }
}