安康做企业网站的,邢台手机网站制作,昆山网站开发公司,wordpress 非法词语文章目录 常用接口介绍PriorityQueue的性质插入/删除/获取优先级最高的元素 top-k问题#xff1a;最大或最小的前k个数堆排序总结 常用接口介绍
PriorityQueue的性质
PriorityQueue默认都是小根堆
public class Test {public static void main(String[] args) {PriorityQue… 文章目录 常用接口介绍PriorityQueue的性质插入/删除/获取优先级最高的元素 top-k问题最大或最小的前k个数堆排序总结 常用接口介绍
PriorityQueue的性质
PriorityQueue默认都是小根堆
public class Test {public static void main(String[] args) {PriorityQueueInteger 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 ComparatorInteger {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();//PriorityQueueInteger 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的使用要注意:
使用时必须导入PriorityQueue所在的包即:import java.util.PriorityQueue;PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出ClassCastException异常不能插入null对象否则会抛出NuliPointerException没有容量限制可以插入任意多个元素其内部可以自动扩容插入和删除元素的时间复杂度为O(log2N)PriorityQueue底层使用了堆数据结构PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素
插入/删除/获取优先级最高的元素
函数名 功能介绍
boolean offer(E e) 插入元素e插入成功返回true如果e对象为空抛出NullPointerException异常时间复杂度 注意空间不够时候会进行扩容E peek() 获取优先级最高的元素如果优先级队列为空返回nullE poll() 移除优先级最高的元素并返回如果优先级队列为空返回nullint size() 获取有效元素的个数voidclear() 清空boolean isEmpty() 检测优先级队列是否为空空返回true
top-k问题最大或最小的前k个数
//把priorityQueue改成大根堆
class Imp implements ComparatorInteger {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;}PriorityQueueInteger 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));}
}堆排序
方法
0下标的数和end的那个数换完之后调用向下调整的方法 判断0下标和它的两个节点哪个大大的数就换到0下标然后end-- end就来到了倒数第二个的数再让0下标的数和end交换换完之后调用向下调整的方法把最大的数移到0下标就这样循环下去二叉树就会按照从小到大的顺序排 //堆排序
public class TestHeap {public void heapSort(){int end usedSize-1;while(end 0){//将0下标和end交换swap(0,end);//向下调整siftDown(0,end);end--;}}总结
关于PriorityQueue的知识就介绍到这里
