建什么网站 做 cpa,自己买域名建设网站,设计模板用什么软件,免费定制开发软件【本节目标】 1. 掌握堆的概念及实现 2. 掌握 PriorityQueue 的使用 一. 优先级队列
1 概念 前面学过队列#xff0c;队列是一种先进先出 (FIFO) 的数据结构 #xff0c;但有些情况下#xff0c; 操作的数据可能带有优先级#xff0c;一般出队 列时#xff0c;可… 【本节目标】 1. 掌握堆的概念及实现 2. 掌握 PriorityQueue 的使用 一. 优先级队列
1 概念 前面学过队列队列是一种先进先出 (FIFO) 的数据结构 但有些情况下 操作的数据可能带有优先级一般出队 列时可能需要优先级高的元素先出队列 该中场景下使用队列显然不合适比如在手机上玩游戏的时候如果有来电那么系统应该优先处理打进来的电话。 在这种情况下数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象 。这种数据结构就是优先级队列 (Priority Queue) 。 2. 优先级队列的模拟实现 JDK1.8中的 PriorityQueue 底层使用了堆这种数据结构 而堆实际就是在完全二叉树的基础上进行了一些调整。 二、堆的概念 如果有一个关键码的集合 K {k0 k1 k2 … kn-1} 把它的所有元素 按完全二叉树的顺序存储方式存储 在一 个一维数组中 并满足 Ki K2i1 且 Ki K2i2 (Ki K2i1 且 Ki K2i2) i 0 1 2… 则 称为 小堆 ( 或大堆) 。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 1.堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树。 2 堆的存储方式 从堆的概念可知堆是一棵完全二叉树因此可以层序的规则采用顺序的方式来高效存储 注意对于 非完全二叉树则不适合使用顺序方式进行存储 因为为了能够还原二叉树 空间中必须要存储空节 点就会导致空间利用率比较低 。 将元素存储到数组中后可以根据二叉树章节的性质 5 对树进行还原。假设 i 为节点在数组中的下标则有 如果i为0则i表示的节点为根节点否则i节点的双亲节点为 (i - 1)/2 如果2 * i 1 小于节点个数则节点i的左孩子下标为2 * i 1否则没有左孩子 如果2 * i 2 小于节点个数则节点i的右孩子下标为2 * i 2否则没有右孩子 3 堆的创建
1 堆向下调整 对于集合 { 27,15,19,18,28,34,65,49,25,37 } 中的数据如果将其创建成堆呢 仔细观察上图后发现根节点的左右子树已经完全满足堆的性质因此只需将根节点向下调整好即可。 向下过程 ( 以小堆为例 ) 1. 让 parent 标记需要调整的节点 child 标记 parent 的左孩子 ( 注意 parent 如果有孩子一定先是有左孩子 ) 2. 如果 parent 的左孩子存在即 :child size 进行以下操作直到 parent 的左孩子不存在 parent右孩子是否存在存在找到左右孩子中最小的孩子让child进行标记将parent与较小的孩子child比较如果 否则交换parent与较小的孩子child交换完成之后parent中大的元素向下移动可能导致子 parent小于较小的孩子child调整结束树不满足此性质因此需要继续向下调整即parent childchild parent*21; 然后继续2。 public void shiftDown(int parent,int usedSize){int childparent*21;while(childusedSize){// 如果右孩子存在找到左右孩子中较大的孩子,用child进行标记if(child1usedSizeelem[child]elem[child1]){child;}if(elem[parent]elem[child]){int tmpelem[parent];elem[parent]elem[child];elem[child]tmp;}else {break;//如果孩子都比父母小}parentchild;child2*parent1;}} 注意在调整以parent为根的二叉树时必须要满足parent的左子树和右子树已经是堆了才可以向下调整。 时间复杂度分析 最坏的情况 即图示的情况 从根一路比较到叶子比较的次数为完全二叉树的高度即时间复杂度为O(logN) 2 堆的创建 那对于普通的序列 { 1,5,3,8,7,6 } 即根节点的左右子树不满足堆的特性又该如何调整呢 public void createHeap(){// 找倒数第一个非叶子节点从该节点位置开始往前一直到根节点遇到一个节点应用向下调整for(int parent(usedSize-1-1)/2;parent0;parent--){shiftDown(parent,usedSize);}} 3 建堆的时间复杂度 因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明( 时间复杂度本来看的就是近似值多几个节点不影响最终结果) 因此 建堆的时间复杂度为 O(N) 。 4 堆的插入与删除
(1) 堆的插入 堆的插入总共需要两个步骤 1. 先将元素放入到底层空间中 ( 注意空间不够时需要扩容 ) 2. 将最后新插入的节点向上调整直到满足堆的性质 public boolean isFull(){if(elem.lengthusedSize){return false;}else {return true;}
}
public void push(int val){//将结点插在最后再向上调整建堆if(isFull()){elem Arrays.copyOf(elem,2*elem.length);}elem[usedSize]val;shiftUp(usedSize);usedSize;
}
public void shiftUp(int child) {int parent(child-1)/2;while(parent0){if(elem[parent]elem[child]){int tmpelem[parent];elem[parent]elem[child];elem[child]tmp;childparent;parent(child-1)/2;}else {break;}}
} 向上调整的时间复杂度为O(NlogN)。 (2) 堆的删除 注意堆的删除一定删除的是堆顶元素。 具体如下 1. 将堆顶元素对堆中最后一个元素交换 2. 将堆中有效数据个数减少一个 3. 对堆顶元素进行向下调整 5 用堆模拟实现优先级队列 public boolean isEmpty(){return usedSize0;}public int poll( ) {if(isEmpty()){return -1;}int valelem[0];swap(elem,0,usedSize-1);shiftDown(0,usedSize-1);usedSize--;return val;}public void swap(int[] elem,int start,int end){int tmpelem[start];elem[start]elem[end];elem[end]tmp;} 常见习题 1. 下列关键字序列为堆的是 :() A: 100,60,70,50,32,65 B: 60,70,65,50,32,100 C: 65,100,70,32,50,60 D: 70,65,100,32,50,60 E: 32,50,100,70,65,60 F: 50,100,70,65,60,32 2. 已知小根堆为 8,15,10,21,34,16,12 删除关键字 8 之后需重建堆在此过程中关键字之间的比较次数是 () A: 1 B: 2 C: 3 D: 4 3. 最小堆 [0,3,2,5,7,4,6,8], 在删除堆顶元素 0 之后其结果是 () A: [3 2 5 7 4 6 8] B: [2 3 5 7 4 6 8] C: [2 3 4 5 7 8 6] D: [2 3 4 5 6 7 8] [ 参考答案 ] 1.A 2.C 3.C 三、常用接口介绍
1 PriorityQueue的特性 Java集合框架中提供了 PriorityQueue 和 PriorityBlockingQueue 两种类型的优先级队列 PriorityQueue 是线 程不安全的 PriorityBlockingQueue 是线程安全的 本文主要介绍 PriorityQueue 。 关于 PriorityQueue 的使用要注意 使用时必须导入PriorityQueue所在的包即 importjava.util.PriorityQueue;PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出 ClassCastException异常 不能插入null对象否则会抛出NullPointerException 没有容量限制可以插入任意多个元素其内部可以自动扩容 插入和删除元素的时间复杂度为O(logN)PriorityQueue底层使用了堆数据结构 PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素
2 PriorityQueue常用接口介绍
1. 优先级队列的构造 此处只是列出了 PriorityQueue 中常见的几种构造方式其他的学生们可以参考帮助文档。 1 PriorityQueue() 2 PriorityQueue(int initialCapacity) 3 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对象来构造一个优先级队列的对象
// q3中已经包含了三个元素PriorityQueueInteger q3 new PriorityQueue(list);System.out.println(q3.size());System.out.println(q3.peek());} 注意默认情况下PriorityQueue 队列是小堆如果需要大堆需要用户提供比较器 // 用户自己定义的比较器直接实现 Comparator 接口然后重写该接口中的 compare 方法即可 public int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
public class Test {public static void main(String[] args) {PriorityQueueInteger priorityQueuenew PriorityQueue(new intCom());priorityQueue.offer(1);priorityQueue.offer(2);priorityQueue.offer(3);System.out.println(priorityQueue.peek());}
} 此时创建出来的就是一个大堆。 2. 插入/删除/获取优先级最高的元素 函数名功能介绍boolean offer(E e)插入元素e插入成功返回true如果e对象为空抛出NullPointerException异常时间复杂度O(logN)注意空间不够时候会进行扩容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()); // 打印优先级队列中有效元素个数System.out.println(q.peek()); // 获取优先级最高的元素
// 从优先级队列中删除两个元素之和再次获取优先级最高的元素q.poll();q.poll();System.out.println(q.size()); // 打印优先级队列中有效元素个数System.out.println(q.peek()); // 获取优先级最高的元素q.offer(0);System.out.println(q.peek()); // 获取优先级最高的元素
// 将优先级队列中的有效元素删除掉检测其是否为空q.clear();if(q.isEmpty()){System.out.println(优先级队列已经为空!!!); 注意以下是 JDK 1.8 中 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来进行扩容 3 oj练习 top-k 问题最大或者最小的前 k 个数据。比如世界前 500 强公司 方法1把所有元素都放去堆排序然后取前K个 class Solution {public int[] smallestK(int[] arr, int k) {PriorityQueueInteger priorityQueuenew PriorityQueue();//O(NlogN)for(int i:arr){priorityQueue.offer(i);}int[] elemnew int[k];//O(klogN)for(int i0;ik;i){elem[i]priorityQueue.poll();}return elem;}
} 时间复杂度O(NlogNklogN)O((Nk)logN) 该解法只是PriorityQueue的简单使用并不是topK最好的做法那topk该如何实现下面介绍 方法2把前K个元素创建为大根堆遍历剩下N-K个元素和堆顶元素相比较如果比堆顶元素小就把堆顶元素删除插入当前元素 class intCom implements ComparatorInteger{public int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}}
class Solution {public int[] smallestK(int[] arr, int k) {int[] elemnew int[k];if(k0||arrnull){return elem;}PriorityQueueInteger priorityQueuenew PriorityQueue(new intCom());//O(klogk)for(int i0;ik;i){priorityQueue.offer(arr[i]);}//O((N-k)logk)for(int jk;jarr.length;j){int peekvalpriorityQueue.peek();if(arr[j]peekval){priorityQueue.poll();priorityQueue.offer(arr[j]);}}for(int i0;ik;i){elem[i]priorityQueue.poll();}return elem;}
} 四. 堆的应用
1 PriorityQueue的实现 用堆作为底层结构 封装优先级队列 2 堆排序 堆排序即利用堆的思想来进行排序总共分为两个步骤 public void shiftDown(int parent,int usedSize){int childparent*21;while(childusedSize){// 如果右孩子存在找到左右孩子中较大的孩子,用child进行标记if(child1usedSizeelem[child]elem[child1]){child;}if(elem[parent]elem[child]){int tmpelem[parent];elem[parent]elem[child];elem[child]tmp;}else {break;//如果孩子都比父母小}parentchild;child2*parent1;}} 1. 建堆 升序建 大堆 降序建小堆 2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。 时间复杂度O(NlogN) 常见习题 1. 一组记录排序码为 (5 11 7 2 3 17), 则利用堆排序方法建立的初始堆为 () A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5) D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5) 答案 C 3 Top-k问题 TOP-K 问题即求数据集合中前 K 个最大的元素或者最小的元素一般情况下数据量都比较大 。 比如专业前10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。 对于Top-K 问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中) 。最佳的方式就是用堆来解决基本思路如下 1. 用数据集合中前 K 个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆 2. 用剩余的 N-K 个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K 个元素依次与堆顶元素比完之后堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。 时间复杂度O(N-k)logk) 树高logk
