Java优先队列 priority queue

目录
  • 1.优先队列概念
  • 2.二叉堆（Heap）
    • 完全二叉树和满二叉树
    • 堆的重要操作

1.优先队列概念

优先队列（priority queue）是一种特殊的数据结构。
队列中每一个元素都被分配到一个优先权值，出队顺序按照优先权值来划分。
一般有两种出队顺序：高优先权出队或低优先权出队。
priority queue至少要有两个最基本的ADT：进队，出队（按照高优先权或低优先权）

产生原因：同样是为了提高数据处理的效率。试想，要实现优先队列对应的功能，若使用链表或者数组，那么要么先排序再插入，要么先插入再查找最大最小元素。这样一来，入队出队的时间复杂度至少为O(N)。

  • 优先队列出队和入队的时间复杂度均为O(log N)。
  • 优先队列基于二叉堆实现。

2.二叉堆（Heap）

堆是一种特殊的二叉树，性质如下：

  • 每个结点的值都大于或等于其左右孩子结点的值（大顶堆），或每个结点的值都小宇或等于其左右孩子的值（小顶堆）。
  • 必须满足完全二叉树的结构。

完全二叉树和满二叉树

完全二叉树 complete binary tree

叶节点只可能出现在最后两层，且最后一层的叶节点都左对齐
一棵深度为h的完全二叉树

满二叉树 full binary tree

深度为h的满二叉树有（2^h）-1个结点

由二叉堆的定义可以看出，跟结点一定是二叉堆中结点值最大（或最小）的。较大（或较小）的结点靠近根节点

堆的存储结构：

一般情况下，堆用数组来存储，第i个结点的父节点的下标就是（i-1）/2.
如果用层序遍历顺序将大顶堆和小顶堆存入数组，

则关系如图：

堆的重要操作

插入：插入一个元素之后，新元素首先被插入表层（即最后一层尽可能左边的位置），之后再根据堆的性质进行调整。

例：写出一次一个地将10,12,1,14,6,5,8,15,3,9,7,4,11,13和2插入一个初始为空的二叉堆的结果

删除：删除总是发生在根处，之后将最后一个元素（即最后一层最右边的元素）拿来填补空缺，之后根据堆的性质进行调整堆的结构。

到此这篇关于Java优先队列 priority queue的文章就介绍到这了,更多相关优先队列 priority queue内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • java优先队列PriorityQueue中Comparator的用法详解

    在使用java的优先队列PriorityQueue的时候,会看到这样的用法. PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){ @Override public int compare(Integer o1, Integer o2){ return o1.compareTo(o2); } }); 那这样到底构造的是最大优先还是最小优先队列呢? 看看源码

  • Java的优先队列PriorityQueue原理及实例分析

    这篇文章主要介绍了Java的优先队列PriorityQueue原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一.优先队列概述 优先队列PriorityQueue是Queue接口的实现,可以对其中元素进行排序, 可以放基本数据类型的包装类(如:Integer,Long等)或自定义的类 对于基本数据类型的包装器类,优先队列中元素默认排列顺序是升序排列 但对于自己定义的类来说,需要自己定义比较器 二.常用方法 peek()//返回队首元素

  • Java优先队列(PriorityQueue)重写compare操作

    we can custom min heap or max heap by override the method compare. package myapp.kit.quickstart.utils; import java.util.Comparator; import java.util.Queue; /** * priority queue (heap) demo. * * @author huangdingsheng * @version 1.0, 2020/5/8 */ publi

  • Java优先队列 priority queue

    Java优先队列 priority queue

    目录 1.优先队列概念 2.二叉堆(Heap) 完全二叉树和满二叉树 堆的重要操作 1.优先队列概念 优先队列(priority queue)是一种特殊的数据结构. 队列中每一个元素都被分配到一个优先权值,出队顺序按照优先权值来划分. 一般有两种出队顺序:高优先权出队或低优先权出队. priority queue至少要有两个最基本的ADT:进队,出队(按照高优先权或低优先权) 产生原因:同样是为了提高数据处理的效率.试想,要实现优先队列对应的功能,若使用链表或者数组,那么要么先排序再插入,要么先

  • Python中的优先队列(priority queue)和堆(heap)

    目录 队列和优先队列(Priority Queue) 堆(heap) 简介 初始化构建堆 堆的插入(节点上浮) 堆的删除(节点下浮) 堆的应用 队列和优先队列(Priority Queue) 队列是一种可以完成插入和删除的数据结构.普通队列是先进先出(FIFO), 即先插入的先被删除. 然而在某些时候我们需要按照任务的优先级顺序来决定出队列的顺序,这个时候就需要用到优先级队列了.优先队列是一种可以完成插入和删除最小元素的数据结构 python中有现成的优先队列类可以调用. 代码示例 from q

  • java队列之queue用法实例分析

    Queue: 基本上,一个队列就是一个先入先出(FIFO)的数据结构 Queue接口与List.Set同一级别,都是继承了Collection接口.LinkedList实现了Deque接 口. Queue的实现 1.没有实现的阻塞接口的LinkedList: 实现了java.util.Queue接口和java.util.AbstractQueue接口 内置的不阻塞队列: PriorityQueue 和 ConcurrentLinkedQueue PriorityQueue 和 Concurren

  • Java Stack与Queue详解

    Java Stack与Queue详解

    一.Stack 示例: package StackPack; import java.util.Stack; public class StackDemo { public static void main(String[] args) { Stack<Integer> stack=new Stack<>(); for(int i=0;i<10;i++) { stack.push(i*2); } //[0, 2, 3, 4, 6, 8, 12, 14, 16, 18] Sys

  • 浅谈Java中的Queue家族

    浅谈Java中的Queue家族

    Queue接口 先看下Queue的继承关系和其中定义的方法: Queue继承自Collection,Collection继承自Iterable. Queue有三类主要的方法,我们用个表格来看一下他们的区别: 方法类型 方法名称 方法名称 区别 Insert add offer 两个方法都表示向Queue中添加某个元素,不同之处在于添加失败的情况,add只会返回true,如果添加失败,会抛出异常.offer在添加失败的时候会返回false.所以对那些有固定长度的Queue,优先使用offer方法.

  • Java中队列Queue和Deque的区别与代码实例

    目录 一.Queue和Deque 二.api对比 三.代码实例 1.queue 2.deque 总结 一.Queue和Deque Queue以及Deque都是继承于Collection,Deque是Queue的子接口. Queue是FIFO的单向队列,Deque是双向队列. Queue有一个直接子类PriorityQueue,而Deque中直接子类有两个:LinkedList以及ArrayDeque. PriorityQueue的底层数据结构是数组,而无边界的形容,那么指明了PriorityQu

  • java中并发Queue种类与各自API特点以及使用场景说明

    java中并发Queue种类与各自API特点以及使用场景说明

    一 先说下队列 队列是一种数据结构．它有两个基本操作:在队列尾部加入一个元素,和从队列头部移除一个元素(注意不要弄混队列的头部和尾部) 就是说,队列以一种先进先出的方式管理数据,如果你试图向一个 已经满了的阻塞队列中添加一个元素或者是从一个空的阻塞队列中移除一个元索,将导致线程阻塞． 在多线程进行合作时,阻塞队列是很有用的工具.工作者线程可以定期地把中间结果存到阻塞队列中而其他工作者线程把中间结果取出并在将来修改它们.队列会自动平衡负载. 如果第一个线程集运行得比第二个慢,则第二个 线程集在等待

  • java实现队列queue数据结构详解

    java实现队列queue数据结构详解

    目录 概念 队列中两个主要操作 队列遵循以下条件: 队列的数组实现 总结 概念 队列是一种非原始(特殊)的线性表,是一种先进先出(FIFO)的数据结构.它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作. FIFO:first input first output,即先添加的元素,先移除,最后添加的元素,最后移除. 工作方式类似于商场排队结账情形: 数组模拟队列图示: 队列中两个主要操作 插入值操作:insert ——> enqueue(入队) ——>参数是要插

  • Java 集合框架 Queue 和 Stack 体系

    Java 集合框架 Queue 和 Stack 体系

    目录 Stack Queue Deque 其他特性 BlockingQueue 特点 PriorityQueue 优先级队列 特点 扩容机制 ArrayDeque 继承关系 底层实现 扩容机制 总结 Stack 栈结构类型,表示对象的后进先出堆栈.Stack 继承自 Vector ,并拓展了五个允许将容器视为栈结构的操作. 包括常见的 pop 和 push 操作.以及查看栈顶元素的方法.检查栈是否为空的方法以及从栈顶向下进行搜索某个元素,并获取该元素在栈内深度的方法. Deque 接口及其实现提

随机推荐