一、优先级队列的概念

二、优先级队列的模拟实现

JDK1.8中PrioorityQueue就是基于使用堆的数据结构实现的，而堆实际是在完全二叉树的基础上进行一些调整来的。

1.堆的概念

小根堆 

2.堆的性质

3.堆的存储方式

从堆的概念可知，堆是一棵完全二叉树，可以采用层序遍历使用顺序的方式来高效存储。

对于完全二叉树来说完全可以采取者中方式，但一般二叉树不能，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。

4.堆的创建

我以大根堆来进行向下调整：

代码展示，如下

public class TestHeap{
public int [] elem;
public int usedSize;
public TestHeap(){
this.elem = new int[10];
}
public void intiElem(int[] arr){
for (int i=0;i<arr.length;i++){
this.elem[i] = arr[i];
usedSize++;
}
}//初始化堆  并且将传入的数组复制到堆数组中， 更新usedSize传入数组的长度

public void creatHeap(){
for(int parent = (this.usedSize-1-1)/2;parent>=0;parent--){
siftDown(parent,this.usedSize);
}/*
1.从最后一个非叶子节点向上调整
2。(this.usedSize-1-1)/2计算最后一个非叶子节点的下标
*/
public void siftDown(int parent,int usedSize){//使用大根堆进行向下调整
int child = 2*parent+1;
while(child<usedSize){
if(child+1<usedSize&&elme[child]<elem[child+1]){
child++;
}
if(child>parent){
swap(int[]elem,child,parent);
parent = child;
 child = 2*parent+1;

}else{
break;
}
}

//只是使用小根堆进行的向下调整
private  void siftDown2(int parent,int usedSize){
        int child = 2*parent+1;
        while (child<usedSize){
            if (child+1<usedSize&&elem[child+1]<elem[child]){
                child++;
            }
            if (elem[child]>elem[parent]){
                swap(elem,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }

    }
public void swap(int[]arr,int i,int j){
int tmp = arr[i];
arr[i] =arr[j];
arr[j] = tmp;
}

 4.1建堆的时间复杂度

给你们一个图并且这是使用错位相减法算出来的

T（N） = n-log2(n+1) 约等于o(N)

 4.2堆的插入和删除

使用代码实现，如下

public void offer(int val){
if(isFull){
elem =Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize] = val;
usedSize++;
}
public boolean isFull(){
return usedSize==elem.length;
}

 上面讲完了向下调整，现在讲向上调整

代码实现，如下

public void siftUp(int Child){
int parent = (Child -1)/2;
while(parent>=0{
if(elem[Child]>elem[parent]){
int tmp = elem[Child];
elem parent = elem[Child];
elem[parent] = tmp;
Child = parent;
parent = (Child-1)/2;
}
}
}

 堆的删除 

public int poll(){
if(isEmpty()){
return -1;
}
int val = elem[0];
elem[0] = elem[--usedSize];
siftDown(0,usedSize-1);
usedSize--;
return val;
}
private boolean isEmpty(){
return usedSize==0;
}

这里有一些习题供大家学习参考

1.下列关键字序列为堆的是:()

A: 100,60,70,50,32,65    B: 60,70,65,50,32,100    C: 65,100,70,32,50,60

D: 70,65,100,32,50,60    E: 32,50,100,70,65,60    F: 50,100,70,65,60,32

2.已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是()

A: 1    B: 2    C:3      D: 4   

 

4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是()

A: [3，2，5，7，4，6，8]     B: [2，3，5，7，4，6，8]

C: [2，3，4，5，7，8，6]     D: [2，3，4，5，6，7，8]

[参考答案]

1.A 2.C 4.C

三、常用接口介绍

1.PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线

程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。

关于PriorityQueue的使用要注意：

1. 使用时必须导入PriorityQueue所在的包，即：

2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出

ClassCastException异常

3. 不能插入null对象，否则会抛出NullPointerException

4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容

5. 插入和删除元素的时间复杂度为O（log2N）

6. PriorityQueue底层使用了堆数据结构

7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素。

2.PriorityQueue常用接口介绍

构造器	功能介绍
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则会抛IllegalArgumentException异 常
PriorityQueue(Collection<? extends E> c)	用一个集合来创建优先级队列

 代码实现，如下

static void TestPriorityQueue(){
PriorityQueue<Integer> p1 = new PriorityQueue<>();//默认容量为11

PriorityQueue<Integer> p2 = new PriorityQueue<>();
ArrayList<Integer> list = new ArrayList<>();/// 用ArrayList对象来构造一个优先级队列的对象
list.add(1);
list.add(2);
list.add(3);
list.add(5);
PriorityQueue<Integer> p3 = new PriorityQueue<>(list);//p3中已经包含了3个元素
System.out.println(q3.size());
System.out.println(q3.peek());
}
//注意： 默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
class Intmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
public class Test{
public static void main(String[] args){
PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
p.offer(4);
p.offer(3);
p.offer(2);
p.offer(1);
p.offer(5);
System.out.println(p.peek());
}
}

 

3.堆排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

代码实现，如下

public void heapSort(){
int end = usedSize-1;
while(end>0){
swap(elem,0,end);
end--;
}
}
public void swap(int[] elem,int i,int j){
int tmp =elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}

还有一道习题供大家学习

1.一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为()

A: (11 5 7 2 3 17)   B: (11 5 7 2 17 3)   C: (17 11 7 2 3 5)

D: (17 11 7 5 3 2)  E: (17 7 11 3 5 2)    F: (17 7 11 3 2 5)

答案：C

4.Top-k问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

class IntCmp implements Comparator<Integer>{
 @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
public class Test{
//整体遍历排序
public int[] smallteok(int[] arr,int k){
int[] ret = new int[k];
if(arr==null||k==0){
return ret;
}
PriorityQueue <Integer> p = new PriorityQueue<>();
//k*logK
for(int i=0;i<k;i++){
p.offer(arr[i]);
}
//(n-k)*logK
for (int i=k;i<arr.length;i++){
int peekval = p.peek();
if(arr[i]<peekval){
p.poll();
p.offer(arr[i]);
}
}
for (int i=0;i<k;i++){
ret[i] =p.poll();
}
return ret;
}

//第三种做法
 public  int [] smallestK1(int[] arr,int k){
PriorityQueue <Integer> p = new PriorityQueue<>();
for (int i=;i<arr.length;i++){
p.offer(arr[i]);
}
int[] ret = new int[k];
for(int i=0;i<k;i++){
ret[i] = p.poll();
}
return ret;
}