PriorityQueue(优先级队列总结)

PriorityQueue(优先级队列总结)一,概念队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列 数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数据结构就是优先级队列(PriorityQueue)二,PriorityQueue的特性Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlo.

大家好,又见面了,我是你们的朋友全栈君。

一,概念

  • 队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列
  • 数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue) 

二,PriorityQueue的特性

Java集合框架中提供了PriorityQueuePriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的

三,使用时的注意事项

1. 使用时必须导入PriorityQueue所在的包

import java.util.PriorityQueue;

2. PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出ClassCastException异常

3. 不能插入null对象,否则会抛出NullPointerException

4. 没有容量限制,可以插入任意多个元素,其内部可以自动扩容

5. 插入和删除元素的时间复杂度为\log_{2}N

6. PriorityQueue底层使用了堆数据结构

7. PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素

四,PriorityQueue的构造器(三种)

import java.util.PriorityQueue;

public class MyPriorityQueue {
    public static void method1(){
        //不添加初始容量  默认为11
        PriorityQueue<Integer> p1 = new PriorityQueue<>();

        //添加初始容量为100
        PriorityQueue<Integer> p2 = new PriorityQueue<>(100);

        p1.offer(1);
        p1.offer(2);
        p1.offer(3);
        p1.offer(4);
        p1.offer(5);

        //使用集合容器来进行构造

        PriorityQueue<Integer> p3 = new PriorityQueue<>(p1);

        System.out.println(p3.peek());
        System.out.println(p3.size());
    }

    public static void main(String[] args) {
        method1();
    }
}

PriorityQueue(优先级队列总结)

默认情况下,PriorityQueue队列是小堆,如果需要大堆需要用户提供比较器

    public static void method2(){
        PriorityQueue<Integer> p1 = new PriorityQueue<>();

        p1.offer(10);
        p1.offer(12);
        p1.offer(14);
        p1.offer(16);
        p1.offer(18);

        System.out.println(p1.peek());

        PriorityQueue<Integer> p2 = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        p2.offer(10);
        p2.offer(12);
        p2.offer(14);
        p2.offer(16);
        p2.offer(18);

        System.out.println(p2.peek());
    }

PriorityQueue(优先级队列总结)
五,插入/删除/获取优先级队列的元素以及使用

PriorityQueue(优先级队列总结)PriorityQueue(优先级队列总结)

 

    public static void method3(){
        PriorityQueue<Integer> p = new PriorityQueue<>();

        p.offer(1);
        p.offer(2);
        p.offer(3);
        p.offer(4);
        p.offer(5);

        System.out.print(p.size() + " ");
        System.out.println(p.peek());

        p.poll();
        p.poll();

        System.out.print(p.size() + " ");
        System.out.println(p.peek());

        p.poll();
        p.poll();
        p.poll();

        System.out.print(p.size() + " ");
        System.out.print(p.peek() + " ");
        System.out.println(p.poll() + " ");
        if (p.isEmpty()){
            System.out.println("p is empty!");
        }else{
            System.out.println("p is not empty!");
        }
    }

PriorityQueue(优先级队列总结)

六,堆

1.什么是堆

JDK1.8中的PriorityQueue底层使用了堆的数据结构,而堆实际就是在完全二叉树的基础之上进行了一些元素的调整。
堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树

PriorityQueue(优先级队列总结) 

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.堆的创建

向下调整

    public void shiftDown(int[] array,int parent){
        int child = parent * 2 + 1;
        int size = array.length;

        while(child < size){
            if ((child + 1 < size) && (array[child + 1] < array[child])){
                child = child + 1;
            }

            if (array[parent] <= array[child]){
                break;
            }else{
                int temp = array[parent];
                array[parent] = array[child];
                array[child] = temp;
                parent = child;
                child = parent * 2 + 1;
            }
        }
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

PriorityQueue(优先级队列总结)

堆的创建

    //堆的创建
    public void createHeap(int[] array){
        int root = ((array.length - 2) >> 1);
        for (int i = root; i >= 0 ; i--) {
            shiftDown(array,root);
        }
    }

堆的插入与删除

向上调整 

    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;
            }
        }
    }
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/133261.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • pycharm 编辑器_运行编辑器怎么运行

    pycharm 编辑器_运行编辑器怎么运行作为PyCharm编辑器的起步,我们理所当然的先写一个Helloword,并运行它。(此文献给对IDE不熟悉的初学者)1,新建一个项目File–>NewProject… 2,新建一个文件右键单击刚建好的helloWord项目,选择New–>PythonFile3,输入文件名输入文件名,

  • pycharm修改编码格式_pycharm代码风格

    pycharm修改编码格式_pycharm代码风格本文转自:pycharm自动调整代码格式问题在使用pycharm的代码编辑器时,常常懒得写空格,如下图,但这是不符合代码规范的,而且也会影响可读性。解决方法pycharm有自动调整代码格式的快捷键,默认为Alt+Ctrl+L,按下快捷键后,代码自动填充了空格。…

  • 手把手教你完成图像分类实战——基于卷积神经网络的图像识别

    手把手教你完成图像分类实战——基于卷积神经网络的图像识别在很多的项目中,都会用到图像识别技术。我在智能电子秤的项目中,就使用了简单的图像识别算法来完成对果蔬的分类(三分类)。图像识别中,最常用的框架就是TensorFlow,我们今天就使用这个框架,手把手教学完成图像识别分类。完成一个图像识别模块主要包括四步:采集数据集搭建合适的模型调参、训练并测试完成接口到项目中关于环境的配置我在此处不多赘余描述,可以自行百度搜索,进行环境配置:python3.6+tensorflow+opencv。关于编译器,我在此处推荐spyder。使用起来非常方便,非常

  • 独立成分分析(Independent Components Analysis)「建议收藏」

    独立成分分析(Independent Components Analysis)「建议收藏」首先我们对ICA算法做一些形式化的描述:ICA是用来分离混合源的技术。所以我们准备先混合,再分离,我们定义两个独立的源,上面的称为A,下面的称为B,代码如下: 1然后我们将其线性混合,上面的为A-2*B下面的为1.73*A+3.41*B2之后使用fastica函数,就将两个源分开了:3完整的工程在这里下载:http://research.ics.aalto.fi

  • 智能车电感差比和差加权算法研究

    智能车电感差比和差加权算法研究▲李佳昊王谢援吴涛在研究基于电感的智能车方向控制时发现了弯道拟合度高的差比和差加权算法。本文从算法的发现、算法原理出发对差比和差算法进行描述,并使用MATLAB、Python建模对其弯道拟合度高的特点与其他优势进行证明。关键词:智能车;电感;MATLAB;01引言在研究基于电感的智能车方向控制时,首先使用了较为普遍的电感差比和加权引导方案。调试过程中,发现小车对于弯道的敏感度不理想,故多次尝试修改横纵电感权重,或将代码推翻重写,寻求理想的结果。进行数次代码推翻重写后,偶然产生了一次期望之外的

  • CSS面试题总结[通俗易懂]

    CSS面试题总结[通俗易懂]前面的话小柒前面总结了与HTML相关的面试题,这篇文章总结CSS相关面试题。题目(1)盒子模型的理解?盒模型分为两种:标准模式与混杂模式(IE模式)标准盒子模型IE盒子模型一般的我们所说的width、height都是指标准盒子模型下的width(也就是content)。(2)CSS中哪些属性可以同父元素继承?字体系列:font-family,font-siz…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号