本地做网站图片怎么存,江门seo哪家专业,个人网页生成器,渭南做网站都有哪些⭐ 作者#xff1a;小胡_不糊涂 #x1f331; 作者主页#xff1a;小胡_不糊涂的个人主页 #x1f4c0; 收录专栏#xff1a;浅谈数据结构 #x1f496; 持续更文#xff0c;关注博主少走弯路#xff0c;谢谢大家支持 #x1f496; PriorityQueue 1. 什么是优先级队列… ⭐ 作者小胡_不糊涂 作者主页小胡_不糊涂的个人主页 收录专栏浅谈数据结构 持续更文关注博主少走弯路谢谢大家支持 PriorityQueue 1. 什么是优先级队列2. 模拟实现2.1 堆2.2 堆的存储方式2.3 堆的创建2.3.1 向下调整2.3.2 堆的创建2.3.3 建堆的时间复杂度 2.4 堆的插入与删除2.4.1 插入2.4.2 删除 3. 常用接口介绍3.1 PriorityQueue的特性3.2 常用接口 1. 什么是优先级队列
首先我们知道队列是一种先进先出(FIFO)的数据结构但有些情况下操作的数据可能带有优先级一般出队列时可能需要优先级高的元素先出队列。 该中场景下使用队列显然不合适比如在手机上玩游戏的时候如果有来电那么系统应该优先处理打进来的电话。
在这种情况下数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。
2. 模拟实现
JDK1.8中的PriorityQueue底层使用了堆这种数据结构而堆实际就是在完全二叉树的基础上进行了一些调整。
2.1 堆
如果有一个关键码的集合K {k0k1 k2…kn-1}把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中并满足Ki K2i1 且 Ki K2i2 (Ki K2i1 且 Ki K2i2) i 012…则称为小堆(或大堆)。
将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。 2.2 堆的存储方式
从堆的概念可知堆是一棵完全二叉树因此可以层序的规则采用顺序的方式来高效存储。 对于非完全二叉树则不适合使用顺序方式进行存储因为为了能够还原二叉树空间中必须要存储空节点就会导致空间利用率比较低。 将元素存储到数组中后可以根据二叉树的性质对树进行还原。假设i为节点在数组中的下标则有 如果i为0则i表示的节点为根节点否则i节点的双亲节点为 (i - 1)/2–向下取整如果2 * i 1 小于节点个数则节点i的左孩子下标为2 * i 1否则没有左孩子如果2 * i 2 小于节点个数则节点i的右孩子下标为2 * i 2否则没有右孩子 2.3 堆的创建
2.3.1 向下调整
对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据如果将其创建成堆呢 仔细观察上图后发现根节点的左右子树已经完全满足堆的性质因此只需将根节点向下调整好即可。
向下调整过程(以小堆为例)
让parent标记需要调整的节点child标记parent的左孩子(注意parent如果有孩子一定先是有左孩子)如果parent的左孩子存在即:child size进行以下操作直到parent的左孩子不存在 parent右孩子如果存在找到左右孩子中最小的孩子让child进行标记将parent与较小的孩子child比较如果parent小于较小的孩子child调整结束否则交换parent与较小的孩子child交换完成之后parent中大的元素向下移动可能导致子树不满足对的性质因此需要继续向下调整即parent childchild parent*21然后继续第2步。 代码实现
private void shiftDown(int parent,int len) {int child 2*parent1;//至少有左孩子while (child len) {//左孩子和右孩子比较大小如果右孩子的值小则那么if(child1 len elem[child] elem[child1]) {child child1;}//走完上述if语句在child下标一定保存的是左右两个孩子最小值的下标if(elem[child] elem[parent]) {//交换swap(child,parent);parent child;child 2*parent1;}else {break;}}}private void swap(int i,int j) {int tmp elem[i];elem[i] elem[j];elem[j] tmp;}在调整以parent为根的二叉树时必须要满足parent的左子树和右子树已经是堆了才可以向下调整。 时间复杂度分析最坏的情况即图示的情况从根一路比较到叶子比较的次数为完全二叉树的高度即时间复杂度为O(log2n)。 2.3.2 堆的创建
对于普通的序列{ 1,5,3,8,7,6 }即根节点的左右子树不满足堆的特性又该如何调整呢
public static void createHeap(int[] array) {// 找倒数第一个非叶子节点从该节点位置开始往前一直到根节点遇到一个节点应用向下调整int root ((array.length-1-1)1);//int root ((array.length-1-1)/2);for (; root 0; root--) {shiftDown(array, root);}
}2.3.3 建堆的时间复杂度
因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个节点不影响最终结果) 因此建堆的时间复杂度为O(N)
2.4 堆的插入与删除
2.4.1 插入
堆的插入总共需要两个步骤
先将元素放入到底层空间中(注意空间不够时需要扩容)将最后新插入的节点向上调整直到满足堆的性质
public void shiftUp(int child) {// 找到child的双亲int parent (child - 1) / 2;while (child 0) {// 如果双亲比孩子小parent满足堆的性质调整结束if (elem[parent] elem[child]) {break;}else{// 将双亲与孩子节点进行交换int t elem[parent];elem[parent] elem[child];elem[child] t;// 大的元素向下移动可能到值子树不满足对的性质因此需要继续向上调增child parent;parent (child - 1) / 2;}}}2.4.2 删除
堆的删除一定删除的是堆顶元素。具体如下
将堆顶元素对堆中最后一个元素交换将堆中有效数据个数减少一个对堆顶元素进行向下调整 3. 常用接口介绍
3.1 PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的。 关于PriorityQueue的使用要注意
使用时必须导入PriorityQueue所在的包即import java.util.PriorityQueue;PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出ClassCastException异常不能插入null对象否则会抛出NullPointerException没有容量限制可以插入任意多个元素其内部可以自动扩容插入和删除元素的时间复杂度为O(log2N)PriorityQueue底层使用了堆数据结构PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素
3.2 常用接口
优先级队列的构造
构造器功能介绍PriorityQueue()创建一个空的优先级队列默认容量是11PriorityQueue(intinitialCapacity)创建一个初始容量为initialCapacity的优先级队列注意initialCapacity不能小于1否则会抛IllegalArgumentException异常PriorityQueue(Collection?extends E c)用一个集合来创建优先级队列
上述方法的实现
static void TestPriorityQueue(){// 创建一个空的优先级队列底层默认容量是11PriorityQueueInteger 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对象来构造一个优先级队列的对象PriorityQueueInteger q3 new PriorityQueue(list);System.out.println(q3.size());//4System.out.println(q3.peek());//1
}插入/删除/获取优先级最高的元素
函数名功能介绍boolean offer(E e)插入元素e插入成功返回true如果e对象为空抛出NullPointerException异常时间复杂度O(log2N) 注意空间不够时候会进行扩容E peek()获取优先级最高的元素如果优先级队列为空返回nullE poll()移除优先级最高的元素并返回如果优先级队列为空返回nullint size()获取有效元素的个数void clear()清空boolean isEmpty()检测优先级队列是否为空空返回true
上述功能的实现
static void TestPriorityQueue2(){int[] arr {4,1,9,2,8,0,7,3,6,5};// 一般在创建优先级队列对象时如果知道元素个数建议就直接将底层容量给好// 否则在插入时需要不多的扩容// 扩容机制开辟更大的空间拷贝元素这样效率会比较低PriorityQueueInteger q new PriorityQueue(arr.length);for (int e: arr) {q.offer(e);}System.out.println(q.size()); // 打印优先级队列中有效元素个数 10System.out.println(q.peek()); // 获取优先级最高的元素 0// 从优先级队列中删除两个元素再次获取优先级最高的元素q.poll();q.poll();System.out.println(q.size()); // 打印优先级队列中有效元素个数 8System.out.println(q.peek()); // 获取优先级最高的元素 2q.offer(0);System.out.println(q.peek()); // 获取优先级最高的元素 0// 将优先级队列中的有效元素删除掉检测其是否为空q.clear();if(q.isEmpty()){System.out.println(优先级队列已经为空!!!);}else{System.out.println(优先级队列不为空);}
}PriorityQueue的扩容方式
private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {int oldCapacity queue.length;// Double size if small; else grow by 50%int newCapacity oldCapacity ((oldCapacity 64) ?(oldCapacity 2) :(oldCapacity 1));// overflow-conscious codeif (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);queue Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {if (minCapacity 0) // overflowthrow new OutOfMemoryError();return (minCapacity MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}优先级队列的扩容说明
如果容量小于64时是按照oldCapacity的2倍方式扩容的如果容量大于等于64是按照oldCapacity的1.5倍方式扩容的如果容量超过MAX_ARRAY_SIZE按照MAX_ARRAY_SIZE来进行扩容
