普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。
优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。
操作：
1.往队列中添加数据
2.从队列中获取数据
优先级队列通常采用堆数据结构处理
用数组实现
算法：
先将数据插入到数组末尾，然后进行上浮操作，
如果父节点大于大于该子节点，则执行上浮操作，直到该节点为根节点。
//交换
private void exchange(int i,int j) {
queue[i]=queue[i]+queue[j];
queue[j]=queue[i]-queue[j];
queue[i]=queue[i]-queue[j];
}
//上浮
private void swim(int k) {
while (k > 1 && compare(k>>1, k)) {
exchange(k, k>>1);
k = k>>1;
}
}
算法：
把数组首节点和尾节点交换，删除尾节点，队列元素个数-1，此时队列可能不满足优先队列的条件，需要执行下沉操作。
具体是先比较下沉节点的的两个子节点的元素大小，选择较小的子节点交换，反复进行此操作，直到树的叶子节点。
private void sink(int k) {
while (k<<1 <= n) {
int j = k<<1;
if (j < n && compare(j, j+1))
j++;
if (!compare(k, j))
break;
exchange(k, j);
k = j;
}
}
package com.itdragon.controller;
/**
* 优先级队列（小顶堆）
* @author JIA_JIAJIA
* @website http://www.jiajiajia.club
* @da2019年5月11日
*/
public class PriorityQueue {
/**
* 队列元素
*/
private int queue[];
/**
* 队列长度
*/
int n;
/**
* 循序打印数组中的值，相当于二叉树的层级遍历
*/
public void printf() {
for(int i=1;i<n+1;i++) {
System.out.print(queue[i]+" ");
}
}
/**
* 初始化队列大小
* @param size
*/
public PriorityQueue(int size) {
/**
* 初始化队列的元素数组，和队列大小
*/
queue=new int[size+1];
n=0;
}
/**
* 插入数据到队列中
* @param data
* @return
*/
public boolean insert(int data) {
/**
* 如果数组容量不够则进行扩容操作（在原来数组容量的基础上+10）
*/
if (n >= queue.length - 1)
queue=java.util.Arrays.copyOf(queue,queue.length+10);
queue[++n] = data;
swim(n);
System.out.println(isPriorityQueue());
return true;
}
/***
* 从队列中获取数据
* @return
*/
public int getDate() {
int data = queue[1];
exchange(1, n);
n--;
sink(1);
queue[n+1]=0;
if ((n > 0) && (n == (queue.length - 1) / 4))
queue=java.util.Arrays.copyOf(queue,queue.length/2);
System.out.println(isPriorityQueue());
return data;
}
/**
* 比较元素的大小，queue[i]>queue[j]返回true,queue[i]<queue[j]返回false
* @param i
* @param j
* @return
*/
public boolean compare(int i,int j) {
return queue[i]>queue[j]?true:false;
}
/**
* 交换queue中i位置和j位置的值
* @param i
* @param j
*/
private void exchange(int i,int j) {
/**
* 不用第三个变量做中间变量，交换两个整数变量的值
* 例：
* a=a+b;
* b=a-b;
* a=a-b;
* 这样a,b的值就交换了
*/
queue[i]=queue[i]+queue[j];
queue[j]=queue[i]-queue[j];
queue[i]=queue[i]-queue[j];
}
/**
* 上浮操作
* @param k 数组下标k
*/
private void swim(int k) {
/**
* 对于小顶堆，如果父节点的值大于该子节点，那么交换该节点和父节点，然后继续比较该节点与父节点...
* 直到该节点是根节点。
* 右移（>>）相当于除以2,参考 http://www.jiajiajia.club/blog/artical/200
*
* 用数组表示二叉树，有如下性质
* 子节点的下标位置>>2等于父节点的下标位置。适用于左节点和右节点。
*/
while (k > 1 && compare(k>>1, k)) {
exchange(k, k>>1);
k = k>>1;
}
}
/**
* 下沉操作
* @param k 数组下标k
*/
private void sink(int k) {
/**
* 从头结点开始，如果当前节点还有子节点，则一直判断是否还可以下沉
*/
while (k<<1 <= n) {
int j = k<<1;//
/**
* j当前节点的左节点，compare(j, j+1)是为了比较做节点大，还是右节点大
* 从而可以判断父节点是向左节点下沉，还是右节点下沉，如果是向右节点下沉则j++
*/
if (j < n && compare(j, j+1))
j++;
/**
* 如果父节点小于子节点的最小值，则下沉结束。
*/
if (!compare(k, j))
break;
/**
* 交换子节点和父节点，当前节点变为子节点，继续判断是否还可以下沉
*/
exchange(k, j);
k = j;
}
}
/**
* 判断是否满足堆得性质
* @return
*/
private boolean isPriorityQueue() {
return isPriorityQueue(1);
}
/**
* 递归遍历判断该堆是否满足堆得性质
* @param k
* @return
*/
private boolean isPriorityQueue(int k) {
if (k > n)
return true;
/**
* 左子树下标位置
*/
int left = k<<1;
/**
* 右子树下标位置
*/
int right = k<<1 + 1;
if (left <= n && compare(k, left))
return false;
if (right <= n && compare(k, right))
return false;
/**
* 递归遍历左右子树
*/
return isPriorityQueue(left) && isPriorityQueue(right);
}
}package com.itdragon.controller;
import org.junit.Test;
/**
* @author JIA_JIAJIA
* @website http://www.jiajiajia.club
* @da2019年5月11日
*/
public class TestMain2 {
@Test
public void test() {
PriorityQueue pq=new PriorityQueue(10);
pq.insert(9);
pq.insert(8);
pq.insert(7);
pq.insert(6);
pq.insert(5);
pq.insert(4);
System.out.println(pq.getDate());
pq.printf();
}
}