#include<bits/stdc++.h>
using namespace std;
int main(){
    //创建优先队列的三种最基本方式
    priority_queue<int> q;//默认按照升序
    priority_queue<int,vector<int>,greater<int> > q2;//从小到大
    priority_queue<int,vector<int>,less<int> > q3;//从大到小
    //本质使队列
    //插入，删除，清空，访问，与队列相同
    q.push(5);q.push(6);//插入的数据可以相同，优先队列的优点在于自动调整顺序
    q.pop();//删除堆顶
    while(!q.empty())   {cout<<q.top()<<endl;   q.pop(); } //遍历
    //清空操作
    while(!q.empty()) q.pop();
    return 0;
}
 
 

C++STL中非常有用的一中数据结构就是队列，其中一种很常用的队列是优先队列。优先队列是按找一定排序方式将push进去的元素进行排列。
 
默认排序方式是大顶堆，即值大的在队首，从大到小出队。
 
priority_queue<int> myQ;
	myQ.push(1);
	myQ.push(2);
	myQ.push(3);
	myQ.push(4);
	myQ.push(5);
	cout<<myQ.top()<<endl;
	//输出5
 
还可以从小到大出队，就是小顶堆，不过需要显示改变它的排序方式
 
	priority_queue<int,vector<int>,greater<int> > myQ;
	myQ.push(1);
	myQ.push(2);
	myQ.push(3);
	myQ.push(4);
	myQ.push(5);
	cout<<myQ.top()<<endl;
	//输出1
 
自定义排序
 
下面就简单写一下我们自己实现大顶堆的排序的方法。
 

struct cmp{ 
 
    bool operator()( const int& a , const int& b )const{ 
 
        return a < b ;      //大顶堆 
 
    } 
 
}; 
	priority_queue<int, vector<int>,cmp> myQ;
	myQ.push(1);
	myQ.push(2);
	myQ.push(3);
	myQ.push(4);
	myQ.push(5);
	cout<<myQ.top()<<endl;
	//输出5

 
自定义排序方式同样适用于各种数据类型和自定义结构体。
 
注意：如果自定义排序方式，第二个参数千万不要省略，虽然第二个参数对我们没什么用，但优先队列实际上底层实现的时候需要，所以需要写。
 当不需要自定义排序的话，后两个参数可以省略。

效果展示：
 
 这里我们从数组的一号位置开始存储
 那么在二叉树中的规律是
 parent(i) = i/2;
 leftChild of (i) = 2i;
 rightChild of (i) = 2i+1;
 

 如上图所示，我们发现，连线的间隔越是往后，距离就越大，而且正好是2的倍数，间隔呈现2,4，8那样增长
 
由于 parent(i) = i/2 ,如上图所示， 15位置是 10 ，那么他的父亲节点位置是 5，也就是41,41的位置是5，那么他父亲节点的位置是2，（这里我没有写 0号元素），也就是52
 我们会发现，每一次找父节点都是 当前节点的位置除以2，也就是相当于折半查找。我们知道
 
2的19次方是524 288 ，也就是说第524288位元素，他最多有19个祖宗，也就是说只要查找19次，就跳到了数组的头部
 维持这个大根堆，我们使用 shiftUp 操作，i节点和 第（i/2）位节点（他爸爸）比较，如果i比 他父亲
 要大，就互换，维持大的在上面，小的在下面的结构，这里就有点像冒泡排序那样的交换排序，只要大就交换，不过冒泡是大的放后面
 
注意：这里描述的是优先队列的入队操作，入队使用 shiftUp，出队使用 shiftDown,只要在末尾添加一个元素，就对这最后一个元素执行shiftUp操作
 
public class Main {


    public static void main(String[] args) {

        
        Random r = new Random();
        MaxHeap  p = new MaxHeap(100);
        int n = 50;
        int m =100;
        for(int i=0;i<n;++i) {
            int t = r.nextInt(100);
            p.insert(t);

        }

        p.treePrint();


    }





}





class MaxHeap {
    int[] data;
    int count;
    int capacity;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        data = new int[capacity];
        this.count=0;

    }
    int size() {
        return count;
    }

    public boolean isEmpty() {
        return count==0;
    }
    void insert(int e) {
        data[count+1]=e;
        count++;
        shiftUp(count);
    }

    void swap(int i,int j) {
        if(data[i]==data[j])return;
        data[i]^=data[j];
        data[j]^=data[i];
        data[i]^=data[j];
    }

    void shiftUp(int k) {
        while (k>1&&data[k]>data[k/2])
        {
            swap(k,k/2);
            k/=2;
        }
    }




    public void treePrint() {

        // 最多打印100个元素
        if (size() >= 100) {
            System.out.println("This print function can only work for less than 100 integer");
            return;
        }

        System.out.println("The max heap size is: " + size());
        System.out.println("Data in the max heap: ");
        for (int i = 0; i < size(); i++) {
            // 我们的print函数要求堆中的所有整数在[0, 100]的范围内
            assert (Integer) data[i] >= 0 && (Integer) data[i] < 100;
            System.out.println(data[i] + " ");
        }

        System.out.println();
        System.out.println();

        int n = size();
        int maxLevel = 0;
        int numberPerLevel = 1;
        while (n > 0) {
            maxLevel += 1;
            n -= numberPerLevel;
            numberPerLevel *= 2;
        }

        int maxLevelNumber = (int) Math.pow(2, maxLevel - 1);
        int curTreeMaxLevelNumber = maxLevelNumber;
        int index = 1;
        for (int level = 0; level < maxLevel; level++) {

            String line1 = new String(new char[maxLevelNumber * 3 - 1]).replace('\0', ' ');

            int curLevelNumber = Math.min(count - (int) Math.pow(2, level) + 1, (int) Math.pow(2, level));
            boolean isLeft = true;
            for (int indexCurLevel = 0; indexCurLevel < curLevelNumber; index++, indexCurLevel++) {
                line1 = putNumberInLine((Integer) data[index], line1, indexCurLevel, curTreeMaxLevelNumber * 3 - 1, isLeft);
                isLeft = !isLeft;
            }
            System.out.println(line1);

            if (level == maxLevel - 1) {
                break;
            }

            String line2 = new String(new char[maxLevelNumber * 3 - 1]).replace('\0', ' ');
            for (int indexCurLevel = 0; indexCurLevel < curLevelNumber; indexCurLevel++) {
                line2 = putBranchInLine(line2, indexCurLevel, curTreeMaxLevelNumber * 3 - 1);
            }
            System.out.println(line2);

            curTreeMaxLevelNumber /= 2;
        }
    }


    private String putNumberInLine(Integer num, String line, int indexCurLevel, int curTreeWidth, boolean isLeft) {

        int subTreeWidth = (curTreeWidth - 1) / 2;
        int offset = indexCurLevel * (curTreeWidth + 1) + subTreeWidth;
        assert offset + 1 < line.length();
        if (num >= 10) {
            line = line.substring(0, offset + 0) + num.toString()
                    + line.substring(offset + 2);
        } else {
            if (isLeft) {
                line = line.substring(0, offset + 0) + num.toString()
                        + line.substring(offset + 1);
            } else {
                line = line.substring(0, offset + 1) + num.toString()
                        + line.substring(offset + 2);
            }
        }
        return line;
    }

    private String putBranchInLine(String line, int indexCurLevel, int curTreeWidth) {

        int subTreeWidth = (curTreeWidth - 1) / 2;
        int subSubTreeWidth = (subTreeWidth - 1) / 2;
        int offsetLeft = indexCurLevel * (curTreeWidth + 1) + subSubTreeWidth;
        assert offsetLeft + 1 < line.length();
        int offsetRight = indexCurLevel * (curTreeWidth + 1) + subTreeWidth + 1 + subSubTreeWidth;
        assert offsetRight < line.length();

        line = line.substring(0, offsetLeft + 1) + "/" + line.substring(offsetLeft + 2);
        line = line.substring(0, offsetRight) + "\\" + line.substring(offsetRight + 1);

        return line;
    }





}

在我的上一篇文章（二叉堆的节点插入、删除以及构建过程）中，介绍了二叉堆，包括最大堆和最小堆，优先队列正是基于二叉堆来实现的。
 
目录
 
一、什么是优先队列？
 
二、优先队列的实现
 
1.“上浮”操作（用于优先队列入队）
 
2.“下沉”操作（用于优先队列出队）
 
3.完整代码
 

一、什么是优先队列？
 
我们知道队列的特点是先进先出（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