水果网站模板,可信网站是否必须做,南京市雨花台区建设局网站,建设银行网站首页是多少优先级队列#xff08;堆#xff09; 1. 优先级队列1.1 概念 2. 优先级队列的模拟实现2.1 堆的概念2.2 堆的存储方式2.3 堆的创建2.3.1 堆向下调整2.3.2 堆的创建2.3.3 建堆的时间复杂度 【本节目标】 掌握堆的概念及实现掌握 PriorityQueue 的使用
1. 优先级队列
1.1 概念… 优先级队列堆 1. 优先级队列1.1 概念 2. 优先级队列的模拟实现2.1 堆的概念2.2 堆的存储方式2.3 堆的创建2.3.1 堆向下调整2.3.2 堆的创建2.3.3 建堆的时间复杂度 【本节目标】 掌握堆的概念及实现掌握 PriorityQueue 的使用
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 }中的数据如果将其创建成堆呢 仔细观察上图后发现根节点的左右子树已经完全满足堆的性质因此只需将根节点向下调整好即可。 向下过程(以小堆为例)
让parent标记需要调整的节点child标记parent的左孩子(注意parent如果有孩子一定先是有左孩子)如果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)。
