广州做网站公司电话,申请个人主页网站,ppt模板免费下载免费,邯郸网页目录
1. 优先级队列
1.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 堆的删除
2.5 用堆模拟实现优先级队列
3.常用接口介绍
3… 目录
1. 优先级队列
1.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 堆的删除
2.5 用堆模拟实现优先级队列
3.常用接口介绍
3.1 PriorityQueue的特性
3.2 PriorityQueue常用接口介绍
1. 优先级队列的构造
2. 插入/删除/获取优先级最高的元素
3.3 oj练习
4. 堆的应用
4.1 PriorityQueue的实现
4.2 堆排序
4.3 Top-k问题 1. 优先级队列
1.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 堆的存储方式
从堆的概念可知堆是一棵完全二叉树因此可以层序的规则采用顺序的方式来高效存储。 注意对于非完全二叉树则不适合使用顺序方式进行存储因为为了能够还原二叉树空间中必须要存储空节点就会导致空间利用率比较低。 将元素存储到数组中后可以根据二叉树章节的性质5对树进行还原。假设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 }中的数据如果将其创建成堆呢
仔细观察上图后发现根节点的左右子树已经完全满足堆的性质因此只需将根节点向下调整好即可。 向下过程(以小堆为例) 1. 让parent标记需要调整的节点child标记parent的左孩子(注意parent如果有孩子一定先是有左孩子) 2. 如果parent的左孩子存在即:child size 进行以下操作直到parent的左孩子不存在 parent右孩子是否存在存在找到左右孩子中最小的孩子让child进行标记将parent与较小的孩子child比较如果 parent小于较小的孩子child调整结束否则交换parent与较小的孩子child交换完成之后parent中大的元素向下移动可能导致子树不满足堆的性质因此需要继续向下调整即parent childchild parent*21; 然后继续2的过程。 public void shiftDown(int[] array, int parent) {// child先标记parent的左孩子因为parent可能右左没有右int child 2 * parent 1;int size array.length;while (child size) {// 如果右孩子存在找到左右孩子中较小的孩子,用child进行标记if(child1 size array[child1] array[child]){child 1;} // 如果双亲比其最小的孩子还小说明该结构已经满足堆的特性了if (array[parent] array[child]) {break;}else{// 将双亲与较小的孩子交换int t array[parent];array[parent] array[child];array[child] t;// parent中大的元素往下移动可能会造成子树不满足堆的性质因此需要继续向下调整parent child;child parent * 2 1;}}
} 注意在调整以parent为根的二叉树时必须要满足parent的左子树和右子树已经是堆了才可以向下调整。 时间复杂度分析 最坏的情况即图示的情况从根一路比较到叶子比较的次数为完全二叉树的高度即时间复杂度为O(log2 n) 2.3.2 堆的创建 那对于普通的序列{ 1,5,3,8,7,6 }即根节点的左右子树不满足堆的特性又该如何调整呢 参考代码
public static void createHeap(int[] array) {// 找倒数第一个非叶子节点从该节点位置开始往前一直到根节点遇到一个节点应用向下调整int root ((array.length-2)1);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 (array[parent] array[child]) {break;} else{// 将双亲与孩子节点进行交换int t array[parent];array[parent] array[child];array[child] t;// 小的元素向下移动可能到值子树不满足对的性质因此需要继续向上调增child parent;parent (child - 1) / 1;}}
}
2.4.2 堆的删除 注意堆的删除一定删除的是堆顶元素。具体如下 将堆顶元素对堆中最后一个元素交换将堆中有效数据个数减少一个对堆顶元素进行向下调整 2.5 用堆模拟实现优先级队列 public class MyPriorityQueue {
// 演示作用不再考虑扩容部分的代码private int[] array new int[100];private int size 0;public void offer(int e) {array[size] e; shiftUp(size - 1); //2.4.1 堆的插入}public int poll() {int oldValue array[0];array[0] array[--size];shiftDown(0);return oldValue;}public int peek() {return array[0];}
} 常见习题 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: [3257468] B: [2357468] C: [2345786] D: [2345678] [参考答案] 1.A 2.C 3.C 3.常用接口介绍
3.1 PriorityQueue的特性 Java集合框架中提供了PriorityQueue 和 PriorityBlockingQueue两种类型的优先级队列PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的本文主要介绍PriorityQueue。 关于PriorityQueue的使用要注意 1. 使用时必须导入PriorityQueue所在的包即 import java.util.PriorityQueue; 2. PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出ClassCastException异常 3. 不能插入null对象否则会抛出NullPointerException 4. 没有容量限制可以插入任意多个元素其内部可以自动扩容 5. 插入和删除元素的时间复杂度为O(log2 N) 6. PriorityQueue底层使用了堆数据结构 7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素 3.2 PriorityQueue常用接口介绍
1. 优先级队列的构造
此处只是列出了PriorityQueue中常见的几种构造方式其他的学生们可以参考帮助文档. 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方法即可
class IntCmp implements ComparatorInteger{Overridepublic 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());}
} 此时创建出来的就是一个大堆。
2. 插入/删除/获取优先级最高的元素 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(优先级队列已经为空!!!);} else{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 : AX_ARRAY_SIZE;
}
优先级队列的扩容说明 如果容量小于64时是按照oldCapacity的2倍方式扩容的如果容量大于等于64是按照oldCapacity的1.5倍方式扩容的如果容量超过MAX_ARRAY_SIZE按照MAX_ARRAY_SIZE来进行扩容 3.3 oj练习
top-k问题最大或者最小的前k个数据。比如世界前500强公司 class Solution {public int[] smallestK(int[] arr, int k) {// 参数检测if(null arr || k 0)return new int[0];PriorityQueueInteger q new PriorityQueue(arr.length);// 将数组中的元素依次放到堆中for(int i 0; i arr.length; i){q.offer(arr[i]);} // 将优先级队列的前k个元素放到数组中int[] ret new int[k];for(int i 0; i k; i){ret[i] q.poll();}return ret;}
}
该解法只是PriorityQueue的简单使用并不是topK最好的做法那topk该如何实现下面介绍
4. 堆的应用
4.1 PriorityQueue的实现
用堆作为底层结构封装优先级队列
4.2 堆排序
堆排序即利用堆的思想来进行排序总共分为两个步骤 1. 建堆 升序建大堆降序建小堆 2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。 常见习题 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 4.3 Top-k问题 TOP-K问题即求数据集合中前K个最大的元素或者最小的元素一般情况下数据量都比较大. 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下 1.用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆 2.用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 感谢观看希望对大家有所帮助
