[TOC]
1、优先队列
优先队列是一种高效实现插入和删除最大元素（或者是最小元素）的数据结构，堆是它的高效的实现，两种操作的时间复杂度均为O(log n)
2、典型的应用
- 在N个数中找出最大的K个数（top k）
- 堆排序
3、基于堆高效的实现优先队列
a、一些概念
- 堆有序：一个二叉树的每个结点都大于它的两个子节点，则称这个二叉树堆有序 -->一个堆有序的二叉树的根节点是所有结点中最大的
- 二叉堆：我的理解是一个堆有序的完全二叉树，简称堆。二叉堆的用数组存储（不使用数组的第一个元素），一个大小为N的完全二叉树的高度为log N
b、关键的步骤
- 使得堆有序化的两个操作：上浮（swim）和下沉(sink)
- 插入元素：将新的元素加到数组的末尾,并使这个元素上浮到合适的位置
- 删除最大元素：将数组顶端的元素删去并将最后一个元素放到顶端，然后使之下沉到合适的位置
c、代码实现
/*
* <p>
* 优先队列的实现（基于堆）
* <p>
* 问题： //items = new Item[5]; 为什么这样写会报错
*/
public class MaxPQ<Item extends Comparable<Item>> {
private int N; //堆中元素的个数
private int maxN;
private Item[] items; //存储完全二叉树的数组
public MaxPQ(int maxN) {
this.maxN = maxN;
items = (Item[]) new Comparable[maxN + 1];
//items = new Item[5];
}
//删除最大元素
public Item delMax() {
if (isEmpty()) return null;
Item max = items[1];
items[1] = items[N--];
items[N + 1] = null;
sink(1);
return max;
}
//插入元素
public void insert(Item item) {
if (item == null) throw new NullPointerException("插入元素为空！");
/* if(N >= maxN){
if (less(items[N],item)) items[N] = item;
}else{
items[++N] = item;
}*/
items[++N] = item;
swim(N);
//printAr();
}
private boolean less(Item item, Item item1) {
return item.compareTo(item1) < 0;
}
//上浮
private void swim(int k) {
while (k > 1) {
if (less(k / 2, k))
swap(k, k / 2);
k /= 2;
}
//其实这样写更好
/*while(k > 1 && less(k / 2,k)){
swap(k,k / 2);
k /= 2;
}*/
}
//下沉
private void sink(int k) {
while(2 * k <= N){
int j = 2 * k;
if(j < N && less(j,j + 1)) j ++;
if (!less(k,j)) break;
swap(k,j);
k = j;
}
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
/**
* 几个辅助函数
*/
private void swap(int k, int i) {
Item tmp = items[k];
items[k] = items[i];
items[i] = tmp;
}
private boolean less(int i, int k) {
return items[i].compareTo(items[k]) < 0;
}
public void printAr(){
System.out.println(Arrays.toString(items));
}
}
4、在N个数字中找到最大的M个数大概的思路（用最小堆）
- 将N个数字逐一插入到最小堆中； //插入
- 如果堆中的元素的个数超过了M，则删除最小的元素，直到读完N个数据 //删除优先级最高的元素
剩下的M个元素就是N个数字中最大的M个
5、利用系统自带的PriorityQueue来实现在N个数字中找到最大的M个,这里要用最小堆
PriorityQueue represented as a balanced binary heap(平衡二叉堆),PriorityQueue默认是用最小堆的实现（java默认将最小值放到前面），在它的构造方法里面传一个Collections.reverseOrder()就是一个最大堆的实现
代码:
/**
*
* 主要是为了在N个数字中找到最大的M个
*
* 要找到N个数字中最大的M个要用最小堆，相反要找到N个数字中最小的M个数字要用最大堆。
*
* 大概的思路（在N个数字中找到最大的M个）：
*
* 将N个数字逐一插入到最小堆中；
* 如果堆中的元素的个数超过了M，则删除最小的元素，直到读完N个数据
*
* 剩下的M个元素就是N个数字中最大的M个
*/
public class TestTopM {
public static void main(String[] args) {
TestTopM t = new TestTopM();
//测试PriorityQueue
// t.testPriorityQueue();
//测试MaxPQ
t.testMaxPQ();
//测试排序
// t.testOrder();
}
/**
* java默认是给基本类型的数据从小到大排序
* <p>
* 要给基本类型的数据按从大到小的顺序来排，可以使用包装类并传Collections.reverseOrder()参数；
* 但是这样涉及到数据的装箱与拆箱,所以建议先从小到大排序，然后再逆序
*/
private void testOrder() {
Integer[] ar = {1, 6, 3, 2, 10, 13, 23};
System.out.println(Arrays.toString(ar));
Arrays.sort(ar, Collections.reverseOrder());
System.out.println(Arrays.toString(ar));
}
private void testMaxPQ() {
int M = 5;
MaxPQ<Integer> queue = new MaxPQ<>(M + 1); //由于MaxPQ维护数组的第一个元素没有用到
int[] ar = ArrayUtils.randomArray(10, 1, 15);
ar = new int[]{1, 6, 9, 15, 5, 8, 13, 9, 11, 14};
System.out.println("原数组 ：" + Arrays.toString(ar));
for (int i = 0; i < ar.length; i++) {
queue.insert(ar[i]);
if (queue.size() > M) queue.delMax();
}
Arrays.sort(ar);
System.out.println("排序后的数组 ：" + Arrays.toString(ar));
System.out.println("队列的长度 ：" + queue.size());
//为了从大到小到小输出
ArrayDeque<Integer> stack = new ArrayDeque<>();
while(!queue.isEmpty()){
stack.push(queue.delMax());
}
while (!stack.isEmpty()){
System.out.print(stack.poll() + ",");
}
}
/**
* 利用jdk自带的PriorityQueue来实现在N个数字中找到最大的M个,这里要用最小堆
* <p>
* a、PriorityQueue represented as a balanced binary heap（平衡二叉堆）
* b、PriorityQueue默认是用最小堆的实现（java默认将最小值放到前面），在构造方法里面传一个
* Collections.reverseOrder()就用一个最大堆的实现
* c、插入元素：offer()、add() 找出并删除优先级最高的元素：poll() 找出优先级最高的元素：peek()
*/
void testPriorityQueue() {
int M = 4;
//PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> queue = new PriorityQueue<>();
int[] ar = ArrayUtils.randomArray(10, 1, 15);
System.out.println("原数组 ：" + Arrays.toString(ar));
for (int i = 0; i < ar.length; i++) {
queue.offer(ar[i]);
if (queue.size() > M) queue.poll();
}
Arrays.sort(ar);
ArrayUtils.inverseArray(ar);
System.out.println("排序后的数组 ：" + Arrays.toString(ar));
System.out.println("队列的长度 ：" + queue.size());
//为了从大到小到小输出
ArrayDeque<Integer> stack = new ArrayDeque<>();
while(!queue.isEmpty()){
stack.push(queue.poll());
}
while (!stack.isEmpty()){
System.out.print(stack.poll() + ",");
}
}
}
6、基于堆的排序
- 思路一：利用辅助空间进行：把数组的元素依次放到一个堆里面，然后把堆中的元素放到数组中去，这样的话，从小到大排序要用到的是最小堆。这样做牺牲了一点的空间复杂度为O(N)，虽然简单，但是浪费空间
- 思路二:原地堆排序
分为两步：
a.原地构造堆：从完全二叉树中最后一个叶子节点的的父节点开始（一个节点的树就是一个堆），先构造以这个节点为根节点的堆，重复次步骤直至根节点;
这样每个被遍历到的结点的子树都是一个堆，所以每次构造堆就只要一次sink操作即可
b.下沉排序: 依次交换第一个和最后一个元素，然后下沉第一个元素使得除了被换到后面的元素堆有序，直到所有元素都到被交换过 ，由于第一个是优先级别最大的，
所以下沉排序后的数组的顺序和原来的优先级的顺序相反
这样的实现比较复杂，但是空间复杂度为O（1）
c.堆排序源代码：
/**
*
* 利用优先队列的高效找出最大(或者最小)元素进行排序（要用到缓存数组，不知道这样叫不叫堆排序）
*
*/
public class HeapSort {
public static void main(String[] args) {
int[] ar = ArrayUtils.randomArray(10,1,20);
//ar = new int[]{0,1,2,3,4,5,6,7,8};
System.out.println("原数组 ：" + Arrays.toString(ar));
//sort(ar);
sortInPlace(ar);
System.out.println("变化后的数组：" + Arrays.toString(ar));
}
//使用系统自带的优先队列和实现堆排序
public static void sort(int[] ar){
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int i : ar) queue.offer(i);
for (int i = 0; i < ar.length; i++) ar[i] = queue.poll();
}
/**
* 原地实现堆排序(从小到大的排序和最大的的sink一致)
*
* 分为两步，第一步：堆的构造，第二步：下沉排序
*
* 注意:这里有用数组的第一个位置来存储元素
*/
public static void sortInPlace(int[] ar){
int N = ar.length;
//堆的构造
for (int k = (N - 2) / 2; k >= 0; k--) sink(ar,k,N - 1);
/*System.out.println("堆有序化的数组 ：" +Arrays.toString(ar));
System.out.println("-------------------------");*/
//下沉排序
while(N > 0){
ArrayUtils.swap(ar,0,-- N);
sink(ar,0,N - 1);
}
}
private static void sink(int[] ar, int from, int to) {
// System.out.println("from =" + from);
while((2 * from + 1) <= to){
//System.out.println(Arrays.toString(ar) + " ,from =" + from);
int k = 2 * from + 1;
if (k < to && less(ar[k],ar[k + 1])) k ++;
if(!less(ar[from],ar[k])) break;
ArrayUtils.swap(ar,from,k);
from = k;
}
}
private static boolean less(int i, int j) {
return i < j;
}
}
