网站建设服务多少钱,专业网站制作公司名称,网站更名策划方案,郑州网络推广广告公司文章目录 1.优先级队列概念 #x1f4ae;2.优先级队列的模拟实现#x1f4ae;3.常用接口PrinrityQueue介绍#x1f4ae;4.堆的应用#x1f4ae; 1.优先级队列概念 #x1f4ae; 优先级队列 #xff1a;是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优… 文章目录 1.优先级队列概念 2.优先级队列的模拟实现3.常用接口PrinrityQueue介绍4.堆的应用 1.优先级队列概念 优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。 优先级队列相对于普通队列应该提供两个最基本的操作 1返回最高优先级对象2添加新的对象 2.优先级队列的模拟实现 在JDk1.8中的优先级队列底层使用了堆,而堆实际就是在完全二叉树的基础上进行了一些调整。 2.1堆的概念 堆这种数据结构本质上就是一个完全二叉树 并且堆中某个结点的值总是不大于或不小于其父结点的值 小堆根节点最小的堆满足Ki K2i1 且 Ki K2i2
大堆根节点最大的堆, 满足Ki K2i1 且 Ki K2i2 堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。
2.2堆的存储方式 堆是一棵完全二叉树因此可以层序的规则采用顺序的方式来高效存储 对于非完全二叉树则不适合使用顺序方式进行存储因为为了能够还原二叉树空间中必须要存储空节 点就会导致空间利用率比较低。 i为孩子节点双亲节点为 (i - 1)/2 i为根节点左孩子下标为2 * i 1右孩子下标为2 * i 2 2.3堆的创建
2.3.1堆向下调整以创建大堆为例
分析过程如下: //向下调整private void shiftDown(int parent, int len) {int child 2 * parent 1;//最起码要有左孩子while (child len) {//child1len的设置是为了防止child越界异常//获得左右孩子的最大值if (child 1 len elem[child] elem[child 1]) {child;}//child下标一定是左右孩子 最大值的下标if (elem[child] elem[parent]) {int temp elem[child];elem[child] elem[parent];elem[parent] temp;//继续向下调整parent child;child 2 * parent 1;} else {break;}}}然后通过循环每个结点向下调整然后创建好这棵树 public void createHeap() {//usedSize-1表示最后一个childusedSize-1-1/2表示最后一个父节点for (int parent (usedSize - 1 - 1) / 2; parent 0; parent--) {shiftDown(parent, usedSize);}}时间复杂度分析 第1层需要向下移动h-1层 第2层需要向下移动h-2层 …依次类推 分析过程如下: 2.4堆的插入与删除 2.4.1堆的插入 分析过程如下: 这里以在大根堆前提下插入80为例: 代码如下:
//向上调整private void shiftUp(int child) {int parent (child - 1) / 2;while (child 0) {if (elem[child] elem[parent]) {int tmp elem[child];elem[child] elem[parent];elem[parent] tmp;child parent;parent (child - 1) / 2;} else {break;}}}//插入元素 向上调整public void offer(int val) {if (isFull()) {//扩容elem Arrays.copyOf(elem, 2 * elem.length);}elem[usedSize] val;//11//向上调整shiftUp(usedSize - 1);//10}public boolean isFull() {return usedSize elem.length;}2.4.2堆的删除 分析过程如下: 代码如下: 需要判断堆中元素是否为空的情况 //删除元素public void pop() {if (isEmpty()) {return;}swap(elem, 0, usedSize - 1);usedSize--;shiftDown(0, usedSize);}public void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;}public boolean isEmpty() {return usedSize 0;}选择题练习 4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后其结果是( C ) A: [3257468] B: [2357468] C: [2345786] D: [2345678] 3.常用接口PrinrityQueue介绍
3.1PrinrityQueue的特性 Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列PriorityQueue是线 程不安全的PriorityBlockingQueue是线程安全的本文主要介绍PriorityQueue。 使用注意 PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出ClassCastException异常 不能插入null对象否则会抛出NullPointerException 没有容量限制可以插入任意多个元素其内部可以自动扩容 插入和删除元素的时间复杂度为 PriorityQueue底层使用了堆数据结构 PriorityQueue默认情况下是小堆 —即每次获取到的元素都是最小的元素 3.2 PriorityQueue常见的几种构造方式
static void TestPriorityQueue(){
// 创建一个空的优先级队列底层默认容量是11 PriorityQueueInteger q1 new PriorityQueue();
// 创建一个空的优先级队列底层的容量为initialCapacityPriorityQueueInteger q2 new PriorityQueue(100);ArrayListInteger list new ArrayList(); list.add(4); list.add(3); list.add(2);list.add(1); // 用ArrayList对象来构造一个优先级队列的对象 // q3中已经包含了三个元素 PriorityQueueInteger q3 new PriorityQueue(list); System.out.println(q3.size()); System.out.println(q3.peek());}默认情况下PriorityQueue队列是小堆如果需要大堆需要提供比较器 // 用户自己定义的比较器直接实现Comparator接口然后重写该接口中的compare方法即可
class IntCmp implements ComparatorInteger{ Override
public int compare(Integer o1, Integer o2) { return o2-o1;} }
public class TestPriorityQueue {
public static void main(String[] args) { PriorityQueueInteger 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()); } }此时创建出来的就是一个大堆。 插入删除/获取优先级最高的元素 练习top-k问题 描述求前k个最大的数 适用情况: 在数据量比较大时求数据集合中前K个最大的元素或者最小的元素 思路 1求前K个最大的元素建立大小为K的小根堆 2然后用剩下的集合里面的元素轮流和堆顶元素比较如果剩下集合里面的元素比堆顶的元素大那就替换掉堆顶的元素 3然后向下调整变成新的小根堆此时这个堆中的元素就是前K个最大元素 代码如下
public class Test {//前k个最大的数public static int[] maxK(int[] arr, int k) {int[] ret new int[k];if (arr null || k 0) {return ret;}QueueInteger minHeap new PriorityQueue(k);//总的时间复杂度K * logK (N-K) * logK NlogK//时间复杂度K * logK//1.遍历数组的前k个 放到堆当中for (int i 0; i k; i) {minHeap.offer(arr[i]);}//2.遍历剩下的K-1个每次和堆顶元素进行比较//堆顶元素 小的时候就出堆//时间复杂度 : (N-K) * logKfor (int i k; i arr.length; i) {int val minHeap.peek();if (val arr[i]) {minHeap.poll();minHeap.offer(arr[i]);}}for (int i 0; i k; i) {ret[i] minHeap.poll();}return ret;}public static void main(String[] args) {int[] array {1, 5, 43, 3, 2, 7, 98, 41, 567, 78};int[] ret maxK(array, 3);System.out.println(Arrays.toString(ret));}
} 如果要求前K个最小的元素如何做? 和前面差不多不同的是 1求前K个最小的元素要建立大根堆 2比较的时候谁小就把小的放在堆顶 面试题17.14.求前k个最小数-力扣LeetCode)
class Solution {public int[] smallestK(int[] arr, int k) {int[] ret new int[k];if (arr null || k 0) {return ret;}//PriorityQueue默认建立小根堆但是这里我们要建立大根堆就需要自己实现比较器QueueInteger minHeap new PriorityQueue(k,new ComparatorInteger() {Override//o1-o2就是小根堆public int compare(Integer o1, Integer o2) {return o2-o1;}});//总的时间复杂度K * logK (N-K) * logK NlogK//时间复杂度K * logK//1.遍历数组的前k个 放到堆当中for (int i 0; i k; i) {minHeap.offer(arr[i]);}//2.遍历剩下的K-1个每次和堆顶元素进行比较//堆顶元素 大的时候就出堆//时间复杂度 : (N-K) * logKfor (int i k; i arr.length; i) {int val minHeap.peek();if (val arr[i]) {minHeap.poll();minHeap.offer(arr[i]);}}for (int i 0; i k; i) {ret[i] minHeap.poll();}return ret;}
}4.堆的应用
4.1 PriorityQueue的实现 用堆作为底层结构封装优先级队列 4.2堆排序 堆排序即利用堆的思想来进行排序总共分为两个步骤 建堆
升序建大堆降序建小堆
利用堆删除思想来进行排序 即将第一个元素与最后一个元素交换从上往下调整为大根堆/小根堆最后输出就是一个有序序列 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。 这里要按照从小到大排序就建立大根堆 public static void heapSort(int[] array) {createBigHeap(array);int end array.length - 1;while (end 0) {swap(array, 0, end);shiftDown(array, 0, end);end--;}}private static void createBigHeap(int[] array) {for (int parent (array.length - 1 - 1) / 2; parent 0; parent--) {shiftDown(array, parent, array.length);}}private static void shiftDown(int[] array, int parent, int len) {int child parent * 2 1;//至少有左孩子while (child len) {if (child 1 len array[child] array[child 1]) {//有右孩子且右孩子最大child;}if (array[child] array[parent]) {swap(array, child, parent);parent child;child 2 * parent 1;} else {//child比parent小不需要调整break;}}}同样的如果要从大到小排序就要建立小根堆 练习 分析
