电子商务网站分析,妇科医院网站优化服务商,专业摄影网站推荐,网站建设实训报告心得优先级队列 一、堆的概念特性二、堆的创建1、向下调整算法2、向下调整建堆3、向下调整建堆的时间复杂度 三、堆的插入1、向上调整算法实现插入2、插入创建堆的时间复杂度 三、堆的删除四、Java集合中的优先级队列1、PriorityQueue 接口概述及模拟实现2、如何创建大根堆#xf… 优先级队列 一、堆的概念特性二、堆的创建1、向下调整算法2、向下调整建堆3、向下调整建堆的时间复杂度 三、堆的插入1、向上调整算法实现插入2、插入创建堆的时间复杂度 三、堆的删除四、Java集合中的优先级队列1、PriorityQueue 接口概述及模拟实现2、如何创建大根堆 一、堆的概念特性 堆是具有以下性质的完全二叉树每个结点的值都大于或等于其左右孩子结点的值称为大顶堆大根堆每个结点的值都小于或等于其左右孩子结点的值称为小顶堆小根堆。 从堆的概念可知堆是一棵完全二叉树因此可以使用层序的规则采用顺序的方式来高效存储 将元素存储到数组中后可以根据二叉树的性质对树进行还原 假设i为节点在数组中的下标则有 如果i为0则i表示的节点为根节点否则i节点的双亲节点为 (i - 1)/2如果2 * i 1小于节点个数左孩子存在条件则节点i的左孩子下标为2 * i 1否则没有左孩子如果2 * i 2 小于节点个数右孩子存在条件则节点i的右孩子下标为2 * i 2否则没有右孩子 二、堆的创建
1、向下调整算法
示例将集合{75,20,70,30,50,90,80,60,40}调整为小根堆
通过分析已知集合的 “左右子树均满足小堆的性质” 我们只需要将根节点向下调整到合适的位置使集合整体为小堆即可。具体来说我们可以细化为如下调整方法 每次调整以待调整结点、它的左右孩子结点构成的子树为单元进行“向下调整”每个单元以待调整结点为根节点将左右孩子结点的最小值小堆和根节点进行比较如果根节点min(左孩子右孩子)调整结束否则待调整根节点和[min(左孩子右孩子)]交换交换完成后继续重复这个步骤直到待调整结点为当前子树单元中的最小值或待调整结点不在存在孩子结点调整结束。 按照以上思路下面是详细的代码实现 /*** 小根堆-向下调整算法* param parent 待调整结点* param len 数组长度*/private void shiftDown(int[] array,int parent, int len) {int child 2 * parent 1;//根据完全二叉树性质找到左孩子while (child len) {//childlen判断孩子合法性//满足childlen至少存在左孩子if (child 1 len array[child] array[child 1]) {//存在右孩子且右孩子为左右孩子最小值child;}//此时child一定是左右孩子的最小值的下标if (elem[child] elem[parent]) {//满足条件就交换int tmp array[parent];array[parent] array[child];array[child] tmp;//交换完成后继续以新的位置向下调整parent child;child 2 * parent 1;} else {//array[parent] array[child]调整结束break;}}}小结 在调整以parent为根的二叉树时必须要满足 parent 的左子树和右子树已经是堆了才可以向下调整。向下调整算法的最坏情况为从根一直比较到叶子比较的次数为二叉树的高度时间复杂度为O(log₂N)。 2、向下调整建堆
在上面的探讨中我们知道可以使用向下调整算法将左右子树为堆的完全二叉树序列调整为堆那么如果给出任意的完全二叉树序列左右子树不满足堆的特性我们又该如何调整为堆呢 思路 我们已知使用向下调整算法parent的左右子树必须满足堆的特性对于任意普通完全二叉树序列显然不能直接使用向下算法进行调整。不过我们知道一颗完全二叉树是由一颗颗左右子树构成的虽然一颗普通的完全二叉树不能直接使用向下调整算法但是倒数第一个非叶子结点构成的子树一定可以使用向下调整算法所以如果我们可以先将下面的子树调整为堆在继续对子树的根结点进行调整这样根节点的左右子树就满足了堆的特性可以直接使用向下调整算法。就这样一直向上对根结点进行向下调整直到0下标对应的根节点调整完毕整颗完全二叉树序列就满足了堆的特性了。 例如以序列{50,70,40,90,20,10,80,30,60}为例调整后为{10,20,40,30,70,50,80,90,60}
具体实现 /*** 向下调整建堆* param array*/public void creatHeap(int[] array) {//清晰了思路之后建堆就非常简单了//只需从最后一个非叶子结点开始直到找到下标为0的根节点//每遇到一个结点向下调整调用shiftDown即可for (int parent (array.length-1-1)/2; parent 0 ; parent--) {shiftDown(array,parent,array.length); }}3、向下调整建堆的时间复杂度
假设序列为满叉树假设树高为h则最坏情况下第K层的2^(k-1)个结要向下移动h-k层。
三、堆的插入
1、向上调整算法实现插入
堆的插入相对来说较为简单主要分为以下两步 每次将新节点插入到堆的最后一个节点因为底层维护的是一个一维数组空间不够时要扩容。将新插入的节点 向上调整直到满足堆的性质。 所以说堆的插入并不难理解核心就是对向上调整算法的实现 每次调整以新节点构成的子树为单元进行“向上调整”。由于是在堆的基础上进行插入所以每次调整只需将新节点和根节点进行比较如果 根节点新节点小堆调整结束否则根节点和新节点交换交换完成后继续重复这个步骤直到根节点新节点或调整完下标为0的根节点调整结束。 向上调整代码实现 /*** 向上调整算法-小根堆* param child 插入下标* elem 底层维护的一维数组*/private void shiftUp(int child) {int parent (child-1)/2;根据完全二叉树性质找双亲while (child 0) {//child0判断孩子节点的合法性if (elem[child]elem[parent]) {//满足条件交换int tmp elem[parent];elem[parent] elem[child];elem[child] tmp;//交换完成后继续以新的位置向上调整child parent;parent (child-1)/2;} else {//elem[child]elem[parent],调整结束break;}}}堆的插入代码实现 /*** 插入元素也可以向上调整建堆* param val* return* elem 内部维护数组* usedSize 有效长度*/public boolean offerHeap(int val) {if (isFull()) {//扩容elem Arrays.copyOf(elem,elem.length*2);}elem[usedSize]val;shiftUp(usedSize-1);return true;}public boolean isFull() {return usedSizeelem.length;}小结 堆的插入是在堆的基础上进行的插入。向上调整算法的最坏情况为从叶子节点一直比较到根节点比较的次数为二叉树的高度时间复杂度为O(log₂N)。 2、插入创建堆的时间复杂度
最坏情况下假设堆为一颗满二叉树的高度为h
三、堆的删除 规定堆的删除一定删除的是堆顶元素 思路由于堆的底层维护的是一个一维数组所以每次删除我们先将堆顶元素和堆的最后一个元素交换然后让一维数组的size --最后将交换后的堆顶元素 向下调整 即可。 判断堆是否为空空堆不能删除堆顶元素与堆尾元素交换内部维护数组的有效数据减少 1新的堆顶元素向下调整 代码实现 /*** 删除堆顶元素*/public void pollHeap() {//判空if (isEmpty()) {return;}//交换int tmp elem[usedSize-1];elem[usedSize-1] elem[0];elem[0] tmp;//删除向下调整shiftDown(0,--usedSize);}public boolean isEmpty() {return usedSize 0;}四、Java集合中的优先级队列 1、PriorityQueue 接口概述及模拟实现
上面我们花那么多时间介绍堆就是在为Java集合框架中的PriorityQueue做铺垫 PriorityQueue即优先级队列。优先级队列可以保证每次取出来的元素都是队列中的最小或最大的元素Java优先级队列默认每次取出来的为最小元素。JDK1.8中的PriorityQueue底层使用了堆这种数据结构。 PriorityQueue 注意事项 Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的。使用时必须导入PriorityQueue所在的包import java.util.PriorityQueue;PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出 ClassCastException异常因为 null 无法进行比较和排序因此不能插入null对象否则会抛出NullPointerException没有容量限制可以插入任意多个元素其内部可以自动扩容插入和删除元素的时间复杂度为log₂NPriorityQueue底层使用了堆数据结构默认情况下是小堆如果创建大堆需要在构造方法中传入比较器。 常用的构造方法
构造器功能介绍PriorityQueue()创建一个空的优先级队列默认容量是11PriorityQueue(intinitialCapacity)创建一个初始容量为initialCapacity的优先级队列注意initialCapacity不能小于1否则会抛IllegalArgumentException异常PriorityQueue(Comparator c)传入比较器构造大堆
常用的接口
函数名功能介绍boolean offer(E e)插入元素e插入成功返回true如果e对象为空抛出NullPointerException异常空间不够时候会进行扩容E peek()获取优先级最高的元素如果优先级队列为空返回nullE poll()移除优先级最高的元素并返回如果优先级队列为空返回nullint size()获取有效元素的个数void clear()清空boolean isEmpty()检测优先级队列是否为空空返回true
模拟实现PriorityQueue 由于 PriorityQueue 底层使用的是 堆 这种数据结构所以PriorityQueue中的这些接口函数可以参考上面堆的操作下面给出完整代码大家自行理解
public class PriorityQueue {public int[] elem;//数组public int usedSize;//有序长度public PriorityQueue(){elem new int[11];}//1.判满public boolean isFull() {return usedSizeelem.length;}//2.判空public boolean isEmpty() {return usedSize 0;}//3.插入元素public boolean offerHeap(int val) {if (isFull()) {//扩容elem Arrays.copyOf(elem,elem.length*2);}elem[usedSize]val;shiftUp(usedSize-1);return true;}/*** 向上调整算法小根堆* param child* elem 为底层维护的一维数组*/private void shiftUp(int child) {int parent (child-1)/2;while (child 0) {if (elem[child]elem[parent]) {int tmp elem[parent];elem[parent] elem[child];elem[child] tmp;child parent;parent (child-1)/2;} else {break;}}}//4.删除堆顶元素public void pollHeap() {//判空if (isEmpty()) {return;}//交换int tmp elem[usedSize-1];elem[usedSize-1] elem[0];elem[0] tmp;//删除向下调整shiftDown(0,--usedSize);}/*** 向下调整算法小根堆* param parent 待调整结点* param len 数组长度*/private void shiftDown(int parent, int len) {//有左孩子int child 2 * parent 1;//这里是1while (child len) {//有右孩子if (child 1 len elem[child] elem[child 1]) {child;}//此时childe一定是左右孩子的最小值的下标if (elem[child] elem[parent]) {int tmp elem[parent];elem[parent] elem[child];elem[child] tmp;parent child;child 2 * parent 1;} else {break;}}}//5.清空public boolean isEmpty() {return usedSize 0;}
}2、如何创建大根堆
我们已知默认情况下PriorityQueue 是 小堆如果创建大堆需要用户提供比较器关于比较器我在 简介Object类接口实例深浅拷贝、对象数组排序章节中已有过相关介绍大家可点击连接自行参考这里就不做过多冗余介绍了。
下面我演示一下创建大根堆常用的 3 3 3 中方式以下这 3 种创建方式本质上是没有区别的
方式1 直接创建比较类实现 C o m p a r a t o r Comparator Comparator 接口在构造方法中传入比较类对象。
class Integercmp implements ComparatorInteger{Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
public class Demo {public static void main1(String[] args) {Integercmp cmp new Integercmp();QueueInteger maxHeap new PriorityQueue(cmp);}
}方式2 使用匿名内部类
public class Demo {public static void main2(String[] args) {QueueInteger maxHeap new PriorityQueue(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}});}
}方式3 使用 L a m b d a Lambda Lambda 表达式
public class Demo {public static void main3(String[] args) {QueueInteger maxHeap new PriorityQueue((o1,o2)-{return o2.compareTo(o1);});}
}
文章转载自： http://www.morning.fllfz.cn.gov.cn.fllfz.cn http://www.morning.hhxkl.cn.gov.cn.hhxkl.cn http://www.morning.bpmth.cn.gov.cn.bpmth.cn http://www.morning.qbccg.cn.gov.cn.qbccg.cn http://www.morning.qwwcf.cn.gov.cn.qwwcf.cn http://www.morning.gxwyr.cn.gov.cn.gxwyr.cn http://www.morning.rtqyy.cn.gov.cn.rtqyy.cn http://www.morning.yhgbd.cn.gov.cn.yhgbd.cn http://www.morning.xldpm.cn.gov.cn.xldpm.cn http://www.morning.qbwyd.cn.gov.cn.qbwyd.cn http://www.morning.qytpt.cn.gov.cn.qytpt.cn http://www.morning.tllws.cn.gov.cn.tllws.cn http://www.morning.xsszn.cn.gov.cn.xsszn.cn http://www.morning.rqmr.cn.gov.cn.rqmr.cn http://www.morning.pqwjh.cn.gov.cn.pqwjh.cn http://www.morning.ymmjx.cn.gov.cn.ymmjx.cn http://www.morning.zjcmr.cn.gov.cn.zjcmr.cn http://www.morning.dhyqg.cn.gov.cn.dhyqg.cn http://www.morning.rqqn.cn.gov.cn.rqqn.cn http://www.morning.dygqq.cn.gov.cn.dygqq.cn http://www.morning.pxlsh.cn.gov.cn.pxlsh.cn http://www.morning.grnhb.cn.gov.cn.grnhb.cn http://www.morning.fy974.cn.gov.cn.fy974.cn http://www.morning.mlyq.cn.gov.cn.mlyq.cn http://www.morning.thbnt.cn.gov.cn.thbnt.cn http://www.morning.pgrsf.cn.gov.cn.pgrsf.cn http://www.morning.tbknh.cn.gov.cn.tbknh.cn http://www.morning.rtkgc.cn.gov.cn.rtkgc.cn http://www.morning.qkpzq.cn.gov.cn.qkpzq.cn http://www.morning.ddgl.com.cn.gov.cn.ddgl.com.cn http://www.morning.mqfw.cn.gov.cn.mqfw.cn http://www.morning.hbkkc.cn.gov.cn.hbkkc.cn http://www.morning.jfbrt.cn.gov.cn.jfbrt.cn http://www.morning.qywfw.cn.gov.cn.qywfw.cn http://www.morning.ngzkt.cn.gov.cn.ngzkt.cn http://www.morning.c7625.cn.gov.cn.c7625.cn http://www.morning.pwppk.cn.gov.cn.pwppk.cn http://www.morning.rwnx.cn.gov.cn.rwnx.cn http://www.morning.reababy.com.gov.cn.reababy.com http://www.morning.hous-e.com.gov.cn.hous-e.com http://www.morning.baguiwei.com.gov.cn.baguiwei.com http://www.morning.prmyx.cn.gov.cn.prmyx.cn http://www.morning.xfrqf.cn.gov.cn.xfrqf.cn http://www.morning.yknsr.cn.gov.cn.yknsr.cn http://www.morning.rwlnk.cn.gov.cn.rwlnk.cn http://www.morning.mnclk.cn.gov.cn.mnclk.cn http://www.morning.fqzz3.cn.gov.cn.fqzz3.cn http://www.morning.crsqs.cn.gov.cn.crsqs.cn http://www.morning.bnzjx.cn.gov.cn.bnzjx.cn http://www.morning.gcthj.cn.gov.cn.gcthj.cn http://www.morning.zxhpx.cn.gov.cn.zxhpx.cn http://www.morning.kklwz.cn.gov.cn.kklwz.cn http://www.morning.nlrp.cn.gov.cn.nlrp.cn http://www.morning.rflcy.cn.gov.cn.rflcy.cn http://www.morning.jprrh.cn.gov.cn.jprrh.cn http://www.morning.qsyyp.cn.gov.cn.qsyyp.cn http://www.morning.kdtdh.cn.gov.cn.kdtdh.cn http://www.morning.ntqnt.cn.gov.cn.ntqnt.cn http://www.morning.hcqd.cn.gov.cn.hcqd.cn http://www.morning.rwqk.cn.gov.cn.rwqk.cn http://www.morning.xpwdf.cn.gov.cn.xpwdf.cn http://www.morning.mqfw.cn.gov.cn.mqfw.cn http://www.morning.jpmcb.cn.gov.cn.jpmcb.cn http://www.morning.lzrpy.cn.gov.cn.lzrpy.cn http://www.morning.zypnt.cn.gov.cn.zypnt.cn http://www.morning.rpstb.cn.gov.cn.rpstb.cn http://www.morning.smygl.cn.gov.cn.smygl.cn http://www.morning.mkxxk.cn.gov.cn.mkxxk.cn http://www.morning.dfojgo.cn.gov.cn.dfojgo.cn http://www.morning.txlnd.cn.gov.cn.txlnd.cn http://www.morning.homayy.com.gov.cn.homayy.com http://www.morning.c7623.cn.gov.cn.c7623.cn http://www.morning.fgkrh.cn.gov.cn.fgkrh.cn http://www.morning.krywy.cn.gov.cn.krywy.cn http://www.morning.bgxgq.cn.gov.cn.bgxgq.cn http://www.morning.fktlr.cn.gov.cn.fktlr.cn http://www.morning.qddtd.cn.gov.cn.qddtd.cn http://www.morning.spkw.cn.gov.cn.spkw.cn http://www.morning.yqqxj1.cn.gov.cn.yqqxj1.cn http://www.morning.lqjlg.cn.gov.cn.lqjlg.cn
