一、 优先队列的概述
在前面的数据结构（三）：线性表-栈，队列中记录到，队列是先进先出的结构，元素在队列末端添加，在队列前头删除，若使用该队列的数据结构，则当要找出队列中的最大最小值时，需要遍历队列
对每个元素做比较后得出，这样在实际的生产应用中效率是很低的，这时就需要有一种队列，能快捷的获取队列中的最大或最小值，叫做优先队列。
使用优先队列保存数据元素，能快速的获取队列的最大或最小值，比如计算机中有多个排队的任务，但是需要按照优先级一一执行，此时优先队列的优势便得到了体现，在前一章对堆的记录中
我们发现堆能快速的找到最大或最小值并删除，符合优先队列的应用场景，因此本章我们使用堆来实现最大，最小优先队列和索引优先队列
二、 最小优先队列
1、最小优先队列实际就是一个小顶堆，即每次插入堆中的元素，都存储至堆末端，通过上浮操作比较，小于父节点则和父节点交换元素，直到根结点为止，这样就形成了一个小顶堆。
2、在获取最小值时，由于堆是数组的结构，只需获取根结点的值，即数组下标为1的值即可。
3、获取最小值并删除，则可以交换根结点和尾结点，之后删除尾结点，并对根结点进行下沉操作，保证每个父节点都小于两个左右子树即可
public class MinPriorityQueue
// 初始化堆
private T【】 items;
// 初始化个数
private int N;
/
返回优先队列大小
@return
/
public int size() {
return N;
}
/
队列是否为空
@return
/
public boolean isEmpty() {
return N==0;
}
/
构造方法，传入堆的初始大小
@param size
/
public MinPriorityQueue(int size) {
items = (T【】) new Comparable【size + 1】;
N = 0;
}
/
判断堆中索引i处的值是否小于j处的值
@param i
@param j
@return
/
private boolean bigger(int i, int j) {
return items【i】.compareTo(items【j】) > 0;
}
/
元素位置的交换
@param col
@param i
@param j
/
private void switchPos(int i, int j) {
T temp = items【i】;
items【i】 = items【j】;
items【j】 = temp;
}
/
删除堆中最大的元素，并且返回这个元素
@return
/
public T delMin() {
// 获取根结点最大值
T minValue = items【1】;
// 交换根结点和尾结点
switchPos(1, N);
// 尾结点置空
items【N】 = null;
// 堆数量减1
N--;
// 根结点下沉
sink(1);
return minValue;
}
/
往堆中插入一个元素t
@param t
/
public void insert(T t) {
items【++N】 = t;
swim(N);
}
/
使用上浮算法，使堆中索引k处的值能够处于一个正确的位置
@param k
/
private void swim(int k) {
while (k > 1) {
if (bigger(k / 2, k)) {
switchPos(k, k /2);
}
k = k / 2;
}
}
/
使用下沉算法，使堆中索引k处的值能够处于一个正确的位置
@param k
/
private void sink(int k) {
while (2 k <= N) {
int min;
// 存在右子结点的情况
if (2 k + 1 <= N) {
if (bigger(2 k, 2 k + 1)) {
min = 2 k + 1;
} else {
min = 2 k;
}
} else {
min = 2 * k;
}
// 当前结点不比左右子树结点的最小值小，则退出
if (bigger(min, k)) {
break;
}
switchPos(k, min);
k = min;
}
}
public static void main(String【】 args) {
String【】 arr = { "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E" };
MinPriorityQueue minpq = new MinPriorityQueue(20);
for (String s : arr) {
minpq.insert(s);
}
String del;
while (!minpq.isEmpty()) {
del = minpq.delMin();
System.out.print(minpq.size());
System.out.println(del + ",");
}
}
}
三、 最大优先队列
1、最大优先队列实际就是一个大顶堆，即每次插入堆中的元素，都存储至堆末端，通过上浮操作比较，大于父节点则和父节点交换元素，直到根结点为止，这样就形成了一个大顶堆。
2、在获取最大值时，由于堆是数组的结构，只需获取根结点的值，即数组下标为1的值即可。
3、获取最大值并删除，则可以交换根结点和尾结点，之后删除尾结点，并对根结点进行下沉操作，保证每个父节点都大于两个左右子树即可
public class MaxPriorityQueue
// 初始化堆
private T【】 items;
// 初始化个数
private int N;
/
返回优先队列大小
@return
/
public int size() {
return N;
}
/
队列是否为空
@return
/
public boolean isEmpty() {
return N == 0;
}
/
构造方法，传入堆的初始大小
@param size
/
public MaxPriorityQueue(int size) {
items = (T【】) new Comparable【size + 1】;
N = 0;
}
/
判断堆中索引i处的值是否小于j处的值
@param i
@param j
@return
/
private boolean bigger(int i, int j) {
return items【i】.compareTo(items【j】) > 0;
}
/
元素位置的交换
@param col
@param i
@param j
/
private void switchPos(int i, int j) {
T temp = items【i】;
items【i】 = items【j】;
items【j】 = temp;
}
/
删除堆中最大的元素，并且返回这个元素
@return
/
public T delMax() {
// 获取根结点最大值
T maxValue = items【1】;
// 交换根结点和尾结点
switchPos(1, N);
// 尾结点置空
items【N】 = null;
// 堆数量减1
N--;
// 根结点下沉
sink(1);
return maxValue;
}
/
往堆中插入一个元素t
@param t
/
public void insert(T t) {
items【++N】 = t;
swim(N);
}
/
使用上浮算法，使堆中索引k处的值能够处于一个正确的位置
@param k
/
private void swim(int k) {
while (k > 1) {
if (bigger(k, k / 2)) {
switchPos(k, k / 2);
}
//代码效果参考：http://www.zidongmutanji.com/zsjx/514071.html
k = k / 2;}
}
/
使用下沉算法，使堆中索引k处的值能够处于一个正确的位置
@param k
/
private void sink(int k) {
while (2 k <= N) {
int max;
// 存在右子结点的情况
if (2 k + 1 <= N) {
if (bigger(2 k, 2 k + 1)) {
max = 2 k;
} else {
max = 2 k + 1;
}
} else {
max = 2 * k;
}
// 当前结点比左右子树的最大值大，则退出
if (bigger(k, max)) {
break;
}
switchPos(k, max);
k = max;
}
}
public static void main(String【】 args) {
String【】 arr = { "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E" };
//代码效果参考：http://www.zidongmutanji.com/bxxx/383570.html
MaxPriorityQueue maxpq = new MaxPriorityQueue(20);for (String s : arr) {
maxpq.insert(s);
}
System.out.println(maxpq.size());
String del;
while (!maxpq.isEmpty()) {
del = maxpq.delMax();
System.out.print(del + ",");
}
}
}
