网站建设费算费用还是固定资产,企业网站搭建方案,自助建网站市场,上海企业信用信息公示系统查询入口文章目录 #x1f490;1. 优先级队列1.1 概念 #x1f490;2.堆的概念及存储方式2.1 什么是堆2.2 为什么要用完全二叉树描述堆呢#xff1f;2.3 为什么说堆是在完全二叉树的基础上进行的调整#xff1f;2.4 使用数组还原完全二叉树 #x1f490;3. 堆的常用操作-模拟实现3… 文章目录 1. 优先级队列1.1 概念 2.堆的概念及存储方式2.1 什么是堆2.2 为什么要用完全二叉树描述堆呢2.3 为什么说堆是在完全二叉树的基础上进行的调整2.4 使用数组还原完全二叉树 3. 堆的常用操作-模拟实现3.1 堆的创建3.1.1 堆的向下调整(大根堆为例)3.1.2 建堆的时间复杂度 3.2 堆的插入和删除3.2.1 堆的插入3.2.2 堆的删除 4. PriorityQueue常用接口及特性PriorityQueue的构造优先级队列的扩容源码分析 5. PriorityQueue的比较方式6. 例子使用优先级队列解决TOP-k问题 1. 优先级队列
1.1 概念
队列是一种先进先出的数据结构但是呢有时候数据之间也会有优先级就比如说我们想要拿到一个集合中的前k大的数据或者是在平时我们在打游戏时这时候来电话了但是游戏也不能让他退出呀这时候就会忽略掉电话由此可见游戏的优先级要比电话的优先级更高
2.堆的概念及存储方式
优先级队列是由堆实现的 而堆实际实际上是在完全二叉树的基础上进行了调整而此时也就用到了 二叉树的顺序存储方式 这句话是什么意思呢请看下图
2.1 什么是堆
这里不做详细的介绍只需知道所有引用类型所创建的对象都保存在堆上包括数组而这里的堆是将所有的元素按照完全二叉树的顺序存储方式存储到了一维数组中 2.2 为什么要用完全二叉树描述堆呢 2.3 为什么说堆是在完全二叉树的基础上进行的调整
堆又分为了大根堆和小根堆 从上图就可以发现两个性质
1.大根堆中所有的父节点都比子节点大
2.小根堆中所有的父节点都比子节点小
2.4 使用数组还原完全二叉树
在二叉树文章中提到过这样一条性质如果每一个节点都有一个编号 i 的话那么
1.当 i 0 时i 节点的父亲节点为: (i - 1) / 2;
2.如果 2i 1 节点的总数时则下标为 i 节点的左孩子节点的下标为 2i 1
3.如果 2i 2 节点的总数时 则下标为 i 的节点的左孩子节点的下标为 2i 1
因为是在数组中进行存储的所以完全二叉树中每一个节点的编号都是数组中每一个元素的下标所以这样就可以使用数组来还原完全二叉树然后再对完全二叉树进行调整 在上一篇文章中对于 优先级队列的概念及存储方式进行了一个详细的讲解那么本篇文章主要是针对优先级队列底层实现大致是什么样子的亲手写一下代码结合图为大家讲解
3. 堆的常用操作-模拟实现
3.1 堆的创建
我们知道在上一篇文章中讲过所有的元素都是在数组中存储的那么如何利用数组来实现 大根堆 和 小根堆的创建呢就要考虑下面这个问题
如果出现子节点比父节点大或者小该怎么办呢怎么去调整呢
3.1.1 堆的向下调整(大根堆为例) 可以看出最后一棵子树的子节点比父节点大我们所用的方法就是 代码实现
public class MyPriorityQueue {//底层数组private int[] element;//数组中的元素private int usedSize;//初始默认容量private static final int default_capacity 9;public MyPriorityQueue(int[] arr) {this.element new int[default_capacity];//传入一个数组对element进行构造for(int i 0; iarr.length; i) {element[i] arr[i];usedSize;}}//建一个大根堆public void buildHeap() {//parent 求出最后一棵子树的父亲节点for(int parent (usedSize-2)/2; parent 0; parent--) {/*为什么减2而不是减1呢因为如果是最后一个节点的下标值就是减一但是数组的长度值比下标大1所以减2*///向下调整shiftDown(parent, usedSize);}}private void shiftDown(int parent, int len) {//求左孩子节点int child (2*parent)1;//判断是否有右孩子节点并且判断左孩子节点是否大于右孩子节点if(child1 len element[child] element[child1]){//得到最大的孩子节点child;}//判断孩子节点是否比父亲节点大if(element[child] element[parent]) {//进行交换swap(parent, child);}}private void swap(int parent, int child) {int tmp element[parent];element[parent] element[child];element[child] tmp;}public static void main(String[] args) {//测试用例int[] ele {50, 45, 40, 20, 25, 35, 30, 10, 60};MyPriorityQueue myPriorityQueue new MyPriorityQueue(ele);myPriorityQueue.buildHeap();}但是上述代码存在一个致命的问题 代码优化 private void shiftDown(int parent, int len) {//求左孩子节点int child (2*parent)1;while(child len) {//判断是否有右孩子节点并且判断左孩子节点是否大于右孩子节点if(child1 len element[child] element[child1]){//得到最大的孩子节点child;}//判断孩子节点是否比父亲节点大if(element[child] element[parent]) {//进行交换swap(parent, child);//保证交换后该树的子树仍然是大根堆parent child;child (2*parent)1;}else {//表示以该节点为根的树已经是大根堆了break;}}}3.1.2 建堆的时间复杂度
在学会了建堆以后接下来就聊一聊建堆所用的复杂度吧先说结论最坏的情况是O(n),下面我来推到以下
在推导之前先说明一下因为堆是完全二叉树而满二叉树也是完全二叉树多几个节点也无所谓时间复杂度本来就是一个近似值所以为了容易理解这里会用满二叉树进行推导 3.2 堆的插入和删除
3.2.1 堆的插入
堆的插入分为两个步骤
1.将要添加的元素放在底层数组的最后一个位置注意是否要扩容问题
2.向上调整该元素
下面讲解一下什么是向上调整
直接拿要添加的元素与根节点相比较因为本身已经是大根堆了直接与根节点比较符合条件就交换不需要再与其他的节点比较 代码实现 //插入方法public void offer(int val) {//判断是否需要扩容if(is_full()) {this.element Arrays.copyOf(element, element.length1);}//向上调整this.element[usedSize] val;shiftUp();usedSize;}//向上调整private void shiftUp() {int parent (usedSize-1)/2;int child usedSize;while(child 0) {if(element[parent] element[child]) {swap(parent, child);}child parent;parent (child-1)/2;}}private boolean is_full() {return usedSize element.length;}3.2.2 堆的删除
1.将第一个元素和最后一个元素进行交换
2.节点实际上并没有被删除而是节点的个数useSize减1
3.最后向上调整 代码实现 //删除public void poll() {//排除空堆情况if(usedSize 0) {return;}//交换第一个和最后一个元素swap(0,usedSize-1);//节点个数减1不会对最后一个元素进行判断usedSize--;for(int parent (usedSize-1)/2; parent 0; parent--) {//向下调整shiftDown(parent, usedSize);}}private void shiftDown(int parent, int len) {//求左孩子节点int child (2*parent)1;while(child len) {//判断是否有右孩子节点并且判断左孩子节点是否大于右孩子节点if(child1 len element[child] element[child1]){//得到最大的孩子节点child;}//判断孩子节点是否比父亲节点大if(element[child] element[parent]) {//进行交换swap(parent, child);//保证交换后该树的子树仍然是大根堆parent child;child (2*parent)1;}else {//表示以该节点为根的树已经是大根堆了break;}}}4. PriorityQueue常用接口及特性
Java的集合框架中提供了PriorityQueue 和PriorityBlockingQueue两种类型的优先级队列 PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的本篇文章主要介绍PriorityQueue
PriorityQueue的构造
构造器功能讲解PriorityQueue()创建一个空的优先级队列默认容量是11PriorityQueue(int initialCapacity)创建一个初始容量为intialCapacity的优先级队列注意initialCapacity不能小于1 否则会抛出IllegalArgumentException异常PriorityQueue(Collection? extends E c)用一个集合来创建优先级队列PriorityQueue(Comparator? super E comparator)自定义类型进行比较传入一个比较器
代码实现 public static void main(String[] args) {//创建一个空的优先队列底层默认容量是11PriorityQueueInteger priorityQueue1 new PriorityQueue();//创建一个空的优先级队列指定容量为100PriorityQueueInteger priorityQueue2 new PriorityQueue(100);ListInteger list new ArrayList();list.add(1);list.add(2);list.add(3);//使用其他集合构造优先级队列PriorityQueueInteger priorityQueue3 new PriorityQueue(list);//默认是小根堆想要变成大根堆需要传入比较器PriorityQueueInteger priorityQueue4 new PriorityQueue(new com());priorityQueue4.offer(1);priorityQueue4.offer(2);priorityQueue4.offer(3);}//定义一个比较器
class com implements ComparatorInteger {Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
}PriorityQueue使用时需要注意
1.使用时必须导入PriorityQueue所在的包即
import java.until.PriorityQueue;PriorityQueue中放置的元素必须要能够比较大小不能插入不能比较大小的队象否则会抛出ClassCastException异常不能插入 null对象 否则会抛出NullPointerException没有容量限制可以插入多个元素其内部可以自动扩容插入和删除元素的时间复杂度为O(log2N)PriorityQueue底层使用了堆数据结构PriorityQueue默认情况下是小根堆
Java中提供的方法
函数功能介绍boolean offer(E e)插入元素e 插入成功返回true如果e为空抛出异常空间不够时会进行扩容E peek()获取优先级最高的元素如果优先级队列为空放回nullE pool()移除优先级最高的元素如果优先级队列为空返回nullint size()获取有效元素个数void clear()清空boolean isEmpty()检测优先级队列是否为空如果为空返回true
优先级队列的扩容源码分析 5. PriorityQueue的比较方式
PriorityQueue底层使用堆结构所以内部的元素必须能够比较大小PriorityQueue采用了Comparble 和 Comjparator两种方式。 Comparble默认的内部比较方式如果用户插入自定义类型对象是该类对象必须要实现Comparble接口并且要重写compareTo方法 也可以使用比较器用户自己实现一个比较器类且实现Comaparator接口并且让该类重写compare方法指定根据对象的什么内容进行比较然后再实例化PriorityQueue对象时把比较器传进去
源码讲解 //内部定义的比较器对象private final Comparator? super E comparator;//如果用户没有提供比较器则使用内部的比较方式将comparator置为nullpublic PriorityQueue() {this(DEFAULT_INITIAL_CAPACITY, null);}//如果用户提供了比较器则采用提供的比较器进行比较public PriorityQueue(int initialCapacity,Comparator? super E comparator) {// Note: This restriction of at least one is not actually needed,// but continues for 1.5 compatibilityif (initialCapacity 1)throw new IllegalArgumentException();this.queue new Object[initialCapacity];this.comparator comparator;}//在添加对象时进行向上调整//如果没有提供比较器则采用内部比较方式即Comparable//如果提供了比较器则采用比较器进行比较private void siftUp(int k, E x) {if (comparator ! null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);}//采用comparable进行比较private void siftUpComparable(int k, E x) {Comparable? super E key (Comparable? super E) x;while (k 0) {int parent (k - 1) 1;Object e queue[parent];if (key.compareTo((E) e) 0)break;queue[k] e;k parent;}queue[k] key;}//采用comparator进行比较private void siftUpUsingComparator(int k, E x) {while (k 0) {int parent (k - 1) 1;Object e queue[parent];if (comparator.compare(x, (E) e) 0)break;queue[k] e;k parent;}queue[k] x;}6. 例子使用优先级队列解决TOP-k问题
TOP-K 问题求数据集合中前K个最大的元素或者最小的元素一般数据量都比较大
[面试题 17.14. 最小K个数 - 力扣LeetCode]()
class Solution {public int[] smallestK(int[] arr, int k) {//创建一个优先级队列PriorityQueueInteger heap new PriorityQueue();//将所有元素加入到队列中for(int i 0; iarr.length; i) {heap.add(arr[i]);}//创建一个数组用来存储前k个元素int[] ans new int[k];//将堆中的前k个元素保存在数组中for(int i 0; ik; i) {ans[i] heap.poll();}//返回数组return ans;}
}但是上面这个代码只能针对于数据量较小时才行如果数据量太大就会造成时间复杂度过高比如有一亿个数据如果使用以上代码的话会先将一亿个数据都保存在堆中然后进行比较这就得不偿失了那么就要对代码进行一个优化
1.用集合中的前k个元素建堆
前k大个元素建小堆前k小个元素建大堆
2.用剩余的n(元素的个数) - k个元素与堆中的元素进行比较最后堆中剩余的元素就是前k个最大或最小的元素
代码实现 public int[] smallestK(int[] arr, int k) {//求前k个最小元素所以要建大根堆因为PriorityQueue默认的是小根堆所以要传入比较器PriorityQueueInteger heap new PriorityQueue(new Com());//将前k个元素加入到堆中for(int i 0; ik; i){heap.add(arr[i]);}if(heap.isEmpty()) {return new int[]{};}//用剩余的元素与堆顶元素比较for(int i k; iarr.length; i) {int x heap.peek();//这里的条件语句求的是前k个最小元素if(arr[i] x){heap.poll();heap.offer(arr[i]);}}int[] ans new int[k];for(int i 0; ik; i){ans[i] heap.poll();}return ans;}
}
//自定义一个比较器
class Com implements ComparatorInteger {Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}
}
