在我的上一篇文章（二叉堆的节点插入、删除以及构建过程）中，介绍了二叉堆，包括最大堆和最小堆，优先队列正是基于二叉堆来实现的。

一、什么是优先队列？

我们知道队列的特点是先进先出（FIFO），第一个进队列的元素最先出队，而优先队列的出队顺序，不是按照入队顺序来排序的。

在一个最大优先队列中，无论入队顺序如何，都是当前最大的元素优先出队。
在一个最小优先队列中，无论入队顺序如何，都是当前最小的元素优先出队。

当然，我们可以用线性的数据结构来实现最大优先队列和最小优先队列，但是算法的时间复杂度会比较高O(n)。

二、优先队列的实现

若我们采用最大堆来实现最大优先队列，栈顶元素就是最大元素，那么每次入队时，都将元素插在二叉堆最后一个位置，然后进行“上浮”操作（此时是将较大的值往上移）；在出队时，即是删除堆顶节点，然后将最后一个节点替换到堆顶位置，再进行该节点的“下沉”操作（此时是将较小的值往下移，同样理解为大值上移）。

因为上浮操作和下沉操作的时间复杂度是O(logn)，所以优先队列的入队和出队的时间复杂度也是O(logn)。

先说明一点：构建最大优先队列或者最小优先队列的区别，只是在入队和出队时，“上浮”和“下沉”操作中，变换判断的符号即可。

1.“上浮”操作（用于优先队列入队）

在最大优先队列（对应于最大堆，父节点值大于左右孩子节点）入队时，因为插入的位置在二叉堆的最后位置，若该元素为较大的元素，则需要将该节点进行“上浮”。

“上浮”操作（构建最大堆）的思路：

用childIndex来记录插入的节点位置，用temp值记录需要“上浮”的节点值，将childIndex的值与父节点的值进行比较，若孩子节点的值大于父节点，则进行“上浮”操作：单向赋值（无需实际交换两个值），将父节点值赋给孩子节点，然后将孩子节点指针指向父节点，并重新计算父节点指针。若一直上浮到根节点，此时childIndex=0，那么直接将temp值赋值给根节点，因此循环判断的条件中要加上childIndex > 0.具体的实现为：

//实现一个最大堆
    public void upAdjust(){
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        int temp = array[childIndex];
        while(childIndex > 0 && temp > array[parentIndex]){//若后一个大于号改为小于号，则是最小堆
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

2.“下沉”操作（用于优先队列出队）

在最大优先队列（对应于最大堆）出队时，我们移除堆顶节点，同时将最后一个节点替换堆顶节点，此时需要进行“下沉”操作。

“下沉”操作（构建最大堆）的思路：

用childIndex来记录左右孩子中较大的那个，然后将父节点与该孩子节点进行比较，若孩子节点值大于父节点，则进行“下沉”操作，同样是单向赋值，循环的条件为childIndex < size(数组长度），当父节点值大于等于孩子节点时，退出循环。具体实现为：

public void downAdjust(){
        int parentIndex = 0;
        int childIndex = 1;
        int temp = array[parentIndex];
        while(childIndex < size){
            if(childIndex + 1 < size && array[childIndex+1] > array[childIndex]){//若构建最小堆将后一个大于号改为小于号
                childIndex++;
            }
            if(array[parentIndex] >= array[childIndex])//若构建最小堆将大于等于改为小于等于
                break;
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;//此处一定是parentIndex，因为childIndex可能已经超尺寸了
    }

3.完整代码

下面以最大优先队列的入队和出队为例，给出完整的代码实现。

import java.util.Arrays;

public class PriorityQueue {
    private int[] array;
    private int size;
    public PriorityQueue(){
        array = new int[32];
    }

    //入队（最大优先队列）
    public void enQueue(int key){
        if(size >= array.length)
            resize();
        array[size++] = key;
        upAdjust();//实现最小优先队列，这里将upAjust()改为upAdjust1()即可
    }

    //出队（最大优先队列）
    public int deQueue() throws Exception {
        if(size <= 0)
            throw new Exception("队列为空，不能出队！");
        int head = array[0];
        array[0] = array[--size];
        downAdjust();//实现最小优先队列，这里将downAjust()改为downAdjust1()即可
        return head;
    }

    //实现一个最大堆
    public void upAdjust(){
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        int temp = array[childIndex];
        while(childIndex > 0 && temp > array[parentIndex]){
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

    //实现一个最小堆，只需要将判断条件中的大于号改为小于号即可
    public void upAdjust1(){
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        int temp = array[childIndex];
        while(childIndex > 0 && temp < array[parentIndex]){
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

    //实现一个最大堆
    public void downAdjust(){
        int parentIndex = 0;
        int childIndex = 1;
        int temp = array[parentIndex];
        while(childIndex < size){
            if(childIndex + 1 < size && array[childIndex+1] > array[childIndex]){//最大堆中左右孩子节点取较大的那个进行移动
                childIndex++;
            }
            if(array[parentIndex] >= array[childIndex])
                break;
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;//此处一定是parentIndex，因为childIndex可能已经超尺寸了
    }

    //实现一个最小堆
    public void downAdjust1(){
        int parentIndex = 0;
        int childIndex = 1;
        int temp = array[parentIndex];
        while(childIndex < size){
            if(childIndex + 1 < size && array[childIndex+1] < array[childIndex]){//最小堆中左右孩子节点取较小的那个进行移动
                childIndex++;
            }
            if(temp <= array[childIndex])
                break;
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;//此处一定是parentIndex，因为childIndex可能已经超尺寸了
    }

    public void resize(){
        int newLength = array.length * 2;
        this.array = Arrays.copyOf(this.array,newLength);//剩余长度用0补齐
    }

    public static void main(String[] args) throws Exception{
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(7);
        System.out.println("出队元素： "+priorityQueue.deQueue());
        System.out.println("出队元素： "+priorityQueue.deQueue());
    }
}

运行的结果为：

出队元素： 10
出队元素： 7

原文链接：https://blog.csdn.net/shao_yc/article/details/103393791