【PriorityQueue 之 接口介绍and堆排序】

本文主要是介绍【PriorityQueue 之 接口介绍and堆排序】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

常用接口介绍

PriorityQueue的性质

PriorityQueue默认都是小根堆

public class Test {public static void main(String[] args) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();priorityQueue.offer(10);priorityQueue.offer(5);priorityQueue.offer(6);System.out.println(priorityQueue.poll());//5System.out.println(priorityQueue.poll());//6}
｝

如果要大堆，需要提供比较器
方法：直接实现Comparator接口，然后重写该接口中的compare方法即可

class Imp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);//如果是o1 o2，就是小根堆//02 01就是大根堆}
}
public class Test {public static void main(String[] args) {Imp imp = new Imp();//PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(imp);priorityQueue.offer(10);priorityQueue.offer(5);priorityQueue.offer(6);System.out.println(priorityQueue.poll());//10System.out.println(priorityQueue.poll());//6}
}

关于PriorityQueue的使用要注意:

1. 使用时必须导入PriorityQueue所在的包，即:import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
3. 不能插入null对象，否则会抛出NuliPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5. 插入和删除元素的时间复杂度为O(log2N)
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素

插入/删除/获取优先级最高的元素

函数名 功能介绍

1. boolean offer(E e)
   插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度 ，注意：空间不够时候会进行扩容
2. E peek()
   获取优先级最高的元素，如果优先级队列为空，返回null
3. E poll()
   移除优先级最高的元素并返回，如果优先级队列为空，返回null
4. int size()
   获取有效元素的个数
5. voidclear()
   清空
6. boolean isEmpty()
   检测优先级队列是否为空，空返回true

top-k问题：最大或最小的前k个数

//把priorityQueue改成大根堆
class Imp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);//如果是o1o2，就是小根堆//02 01就是大根堆}
}
public class Test {public static int[] smallestK(int[] array, int k) {int [] ret = new int[k];if(arr == null || k <= 0){return ret;}PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Imp());//1.建立大小为k的大根堆O(k*logk)for (int i = 0;i < k;i++){priorityQueue.offer(array[i]);}//2.遍历剩下的元素for (int i = k;i< array.length;i++){int top = priorityQueue.peek();if (array[i] < top){priorityQueue.poll();priorityQueue.offer(array[i]);}}//把最小值放进ret数组//k*logNfor (int i = 0; i < k; i++) {ret[i] = priorityQueue.poll();}System.out.println(Arrays.toString(ret));return ret;}public static void main(String[] args) {int[] array = {1,3,15,7,19,10};int[] ret = smallestK(array,3);System.out.println(Arrays.toString(ret));}
}

堆排序

方法：

1. 0下标的数和end的那个数换完之后，调用向下调整的方法，
   判断0下标和它的两个节点哪个大，大的数就换到0下标
2. 然后end-- ，end就来到了倒数第二个的数，再让0下标的数和end交换，换完之后，调用向下调整的方法，把最大的数移到0下标
3. 就这样循环下去，二叉树就会按照从小到大的顺序排

    //堆排序
public class TestHeap {public void heapSort(){int end = usedSize-1;while(end > 0){//将0下标和end交换swap(0,end);//向下调整siftDown(0,end);end--;}}
｝

总结

关于PriorityQueue的知识就介绍到这里

这篇关于【PriorityQueue 之 接口介绍and堆排序】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---