精华内容
下载资源
问答
  • 本文实例讲述了Python实现优先级队列的方法。分享给大家供大家参考,具体如下: 问题:要实现一个队列,它能够以给定的优先级对元素排序,且每次pop操作时都会返回优先级最高的那个元素; 解决方案:采用heapq模块...
  • 因此,把具有返回优先级最高的对象和添加新对象操作的数据结构称为优先级队列(PriorityQueue)。 基本特性 使用时必须导入PriorityQueue所在的包: import java.util.PriorityQueue; Prior...

    优先级队列

    概念

    队列是一种先进先出(FIFO)的数据结构。
    但在有些情况下,我们进行操作的数据可能带有优先级,在出队列时可能需要优先级高的先出队列。因此,把具有返回优先级最高的对象和添加新对象操作的数据结构称为优先级队列(PriorityQueue)。

    基本特性

    1. 使用时必须导入PriorityQueue所在的包:
    import java.util.PriorityQueue;
    
    1. PriorityQueue中存放的元素必须是能够比较大小的,不能插入无法比较大小的对象,否则会抛异常。
    2. 不能插入null对象,否则会跑出空指针异常。
    3. 没有容量限制,可以插入任意多个元素,其内部可以自动进行扩容。
    4. 插入和删除元素的时间复杂度为O(logN)。
    5. PriorityQueue的底层结构使用了堆数据结构。(用数组存储数据
      用树来组织数据)
    6. 常见的优先级队列的构造方法:
      在这里插入图片描述
      代码示例:
    public static void TestPriorityQueue(){
    	// 创建一个空的优先级队列,底层默认容量是11
    	PriorityQueue<Integer> q1 = new PriorityQueue<>();
    	// 创建一个空的优先级队列,底层的容量为initialCapacity
    	PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
    	ArrayList<Integer> list = new ArrayList<>();
    	list.add(4);
    	list.add(3);
    	list.add(2);
    	list.add(1);
    	// 用ArrayList对象来构造一个优先级队列的对象
    	// q3中已经包含了三个元素
    	PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
    	System.out.println(q3.size());
    	System.out.println(q3.peek());
    }
    

    默认情.况下,PriorityQueue队列底层默认容量是11.

    1. 优先级队列的扩容方式:
    • 如果容量小于64时,按照oldCapacity*2+2的方式扩容。
    • 如果容量大于等于64,按照oldCapacity*1.5的方式扩容。
    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }
    
    1. 常用方法:
    • boolean offer(E e) :插入元素e,插入成功返回true,如果e对象为空,抛出异常,时间复杂度O(logN) ,注意:空间不够时候会进行扩容
    • E peek() :获取优先级最高的元素,如果优先级队列为空,返回null
    • E poll() :移除优先级最高的元素并返回,如果优先级队列为空,返回null
    • int size() :获取有效元素的个数
    • void clear(): 清空
    • boolean isEmpty() :检测优先级队列是否为空,空返回true
    1. 优先级队列的应用:top-k问题
      例如:
      设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。
    public int[] smallK(int[] arr,int k){
    	if(arr==null||k<=0){
    		return new int[0];
    	}
    	PriorityQueue<Integer> p = new PriorityQueue<>();
    	for(int i = 0;i < arr.length;i++){
    		p.offer(arr[i]);
    	}
    	int[] ret = new int[k];
    	for(int i = 0;i < k;i++){
    		ret[i] = p.poll();
    	}
    	return ret;
    }
    
    展开全文
  • 优先级队列是一种带有优先级的队列,它是一种比栈和队列更为专有的数据结构,与普通队列一样,优先级队列中数据元素按关键字的值有序排列。由于很多情况下,需要访问具有最小关键字值的数据元素(例如要寻找最便宜的...

    *文中内容大多来源于《数据结构 --Java语言描述》(第二版) 刘小晶 杜选 主编
    *此系列文章作为学习记录,若文中内容有误,请大家指出,谢谢

    优先级队列

    优先级队列是一种带有优先级的队列,它是一种比栈和队列更为专有的数据结构,与普通队列一样,优先级队列中数据元素按关键字的值有序排列。由于很多情况下,需要访问具有最小关键字值的数据元素(例如要寻找最便宜的方法或最短的路径去做某件事),因袭,约定关键字最小的数据元素(或者在某些实现中是关键字最大的数据元素)具有最高的优先级,并且总是排在队首。

    接口描述:
    public interface IQueue {
        public void clear();
        public boolean isEmpty();
        public int length();
        public Object peek();       //取队首元素并返回其值
        public void offer(Object x) throws Exception;       //入队操作
        public Object poll();       //出队操作
    }
    
    优先队列中结点data的类描述:
    public class PriorityQData {
        public Object elem;         //结点的数据元素值
        public int priority;        //结点的优先数
    
        public PriorityQData(Object elem, int priority){
            this.elem = elem;
            this.priority = priority;
        }
    }
    
    实现IQueue接口的类描述:
    import Book_U2.Node;
    public class PriorityQueue implements IQueue {
        private Node front;             //队首的引用
        private Node rear;              //队尾的作用
    
        //优先队列类的构造函数
        public PriorityQueue(){
            front = rear = null;
        }
    
        //队列置空
        public void clear(){
            front = rear = null;
        }
    
        //队列判空
        public boolean isEmpty(){
            return front == null;
        }
    
        //求队列长度
        public int length(){
            Node p = front;
            int length = 0;             //队列的长度
            while(p != null){           //一直查找找到队尾
                p = p.next;
                ++length;               //长度增加1
            }
            return length;
        }
    
        //入队
        public void offer(Object x){
            PriorityQData pn = (PriorityQData)x;
            Node s = new Node(pn);      //构造一个新结点
            if (front == null)          //队列为空
                front = rear = s;       //修改队列的首尾结点
            else{
                Node p = front , q = front;
                while(p != null && pn.priority >= ((PriorityQData)p.data).priority){    //新结点的数据域值与队列结点的数据域值相比较
                    q = p;
                    p = p.next;
                }
                if (p == null){             //p为空,表示遍历到了队列尾部
                    rear.next = s;          //将新结点加入到队尾
                    rear = s;               //修改队尾指针
                }
                else if (p == front){       //p的优先级大于队首结点的优先级
                    s.next = front;         //将新结点加入到队首
                    front = s;              //修改队首指针
                }
                else {                      //新结点加入队列中部
                    q.next = s;
                    s.next = p;
                }
            }
        }
    
        //读取队首元素
        public Object peek(){
            if (front == null)              //队列为空
                return null;
            else                            //返回队首结点的数据域值
                return front.data;
        }
    
        //出队
        public Object poll(){
            if (front == null)              //队列为空
                return null;
            else{                           //返回队首结点的数据域值,并修改队首指针
                Node p = front;
                front = p.next;
                return p.data;
            }
        }
    
        //输出所有队列中的所有数据元素(从队首到队尾)
        public void display(){
            if (!isEmpty()){
                Node p = front;
                while(p != rear.next){      //从队首到队尾
                    PriorityQData q = (PriorityQData)p.data;
                    System.out.println(q.elem + " " + q.priority);
                    p = p.next;
                }
            }
            else
                System.out.println("此队列为空");
        }
    }
    
    Node的描述:
    /**
     * data是数据域,用来存放数据元素的值;next是指针域,用来存放后继结点的地址
     */
    public class Node {
        public Object data;    //存放结点值
        public Node next;    //后继结点的引用
    
        //无参数时的构造函数
        public Node(){
            this(null,null);
        }
    
        //带一个参数时的构造函数
        public Node(Object data){
            this(data,null);
        }
    
        //带两个参数时的构造函数
        public Node(Object data,Node next){
            this.data = data;
            this.next = next;
        }
    }
    
    

    并附上一个简易实例

    • 设计一个程序模仿操作系统的进程管理问题。要求按进程服务优先级高的先服务、优先级相同的按先到先服务的原则进行管理。
    • 操作系统中每个进程的模仿数据由进程号和进程优先级两部分组成,进程号是每个不同进程的唯一标识,优先级通常是一个0到40的数值,规定0为优先级最高,40为优先级最低。下面为一组模拟数据:
      | 进程号 | 进程优先级 |
      |1 | 20|
      |2 | 40|
      |3 | 0|
      |4 | 10|
      |5 | 40|
    程序代码
    package Book_U3;
    
    public class Example3_6 {
        public static void main(String[] args){
            PriorityQueue pm = new PriorityQueue();             //构造一个对象
            pm.offer(new PriorityQData(1, 20));  //插入优先级队列
            pm.offer(new PriorityQData(2, 30));
            pm.offer(new PriorityQData(3, 20));
            pm.offer(new PriorityQData(4, 20));
            pm.offer(new PriorityQData(5, 40));
            pm.offer(new PriorityQData(6, 10));
            System.out.println("进程服务的顺序:");
            System.out.println("进程ID进程优先级");
            while(!pm.isEmpty()){           //从队首到队尾,输出结点的数据域值和优先级
                PriorityQData p = (PriorityQData)pm.poll();     //移除队首结点,并返回其数据域值
                System.out.println(" " + p.elem + "\t" + p.priority); //输出
            }
        }
    }
    
    
    展开全文
  • 堆:一棵完全二叉树,是实现优先级队列效率很高的数据结构。 (STL类priority-queue是实现优先级队列) 定义: 优先级队列:0个或多个元素的集合,每个元素具有一个优先权或值。 可完成操作:查找一个元素...

    1 概述

    优先级队列:出队列顺序由元素的优先级决定。
    堆:一棵完全二叉树,是实现优先级队列效率很高的数据结构。
    (STL类priority-queue是用堆实现的优先级队列)

    定义:
    优先级队列:0个或多个元素的集合,每个元素具有一个优先权或值。
    可完成操作:查找一个元素(top)、插入一个元素(push)、删除一个元素(pop)
    分类:最小优先级队列、最大优先级队列
    抽象数据类型
    在这里插入图片描述
    最大优先级队列ADT实现:

    template<class T>
    class maxPriorityQueue 
    {
       public:
          virtual ~maxPriorityQueue() {}
          virtual bool empty() const = 0;
                      // return true iff queue is empty
          virtual int size() const = 0;
                      // return number of elements in queue
          virtual const T& top() = 0;
                      // return reference to the max element
          virtual void pop() = 0;
                      // remove the top element
          virtual void push(const T& theElement) = 0;
                      // add theElement to the queue
    };
    #endif
    

    2 堆

    2.1 定义
    大根树(小根树):每个节点的值都大于(小于)或等于其子节点的值
    在这里插入图片描述
    大根堆(小根堆):既是大根树(小根树),又是完全二叉树。

    完全二叉树:若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

    2.2 操作
    (1)大根堆的插入:
    在这里插入图片描述
    注:插入位置随着插入元素值大小变化,目的是不改变堆的“大根性”
    (2)大根堆的删除
    在这里插入图片描述
    a为上图d删除21的结果;c为继续删除20的结果。
    注:同样保证删除元素后仍是大根堆。
    (3)大根堆的初始化
    从最后一个有孩子的节点开始检查,直至检查到以1为根的树为止。
    在这里插入图片描述
    2.3 实现
    类maxHeap:实现一个最大优先级队列。类的成员是heap(一个类型为T的一维数组)、arrayLength(数组heap的容量)、和heapSize(堆的元素个数)。

    template<class T>
    class maxHeap : public maxPriorityQueue<T>
    {
    public:
    	maxHeap(int initialCapacity = 10);
    	~maxHeap() { delete[] heap; }
    	bool empty() const { return heapSize == 0; }
    	int size() const
    	{
    		return heapSize;
    	}
    	const T& top()
    	{// return max element
    		if (heapSize == 0)
    			throw queueEmpty();
    		return heap[1];
    	}
    	void pop();
    	void push(const T&);
    	void initialize(T*, int);
    	void deactivateArray()
    	{
    		heap = NULL; arrayLength = heapSize = 0;
    	}
    	void output(ostream & out) const;
    private:
    	int heapSize;       // number of elements in queue
    	int arrayLength;    // queue capacity + 1
    	T* heap;            // element array
    };
    

    3 左高树

    2.1 定义
    高度优先左高树(HBLT):当且仅当其任何一个内部节点的左孩子s值都大于或等于右孩子的s值
    重量优先左高树(WBLT):当且仅当任何一个内部节点的左孩子的w值都大于或等于右孩子的s值

    性质:
    (1)以x为根的子树节点数目至少为 2 s ( x ) − 1 2^{s(x)}-1 2s(x)1
    (2)以x为根的子树有m个节点, s ( x ) s(x) s(x)最多为 l o g 2 ( m + 1 ) log_2{(m+1)} log2(m+1)
    (3)从x到外部节点的最右路径的长度为 s ( x ) s(x) s(x)

    在这里插入图片描述
    2.2 最大HBLT 操作
    插入:通过合并操作来实现,先建立一颗只有待插入元素的HBLT,然后与原来的合并
    删除:根 被删除时,分别以左右孩子为根的子树是两颗最大 HBLT,将其合并
    合并:n个元素的HBLT,最右路径为 O ( l o g n ) O(logn) O(logn),故合并过程通过遍历其最右路径展开。合并策略最好通过递归实现。首先比较两个根元素,较大者为合并后的根。例如A、B进行合并时,A根最大,则用B和A的右子树合并得到C,比较C和L的s值,大者为合并后的左子树。
    例子:
    (1)
    在这里插入图片描述
    (2)
    在这里插入图片描述
    (3)
    在这里插入图片描述
    (4)
    在这里插入图片描述
    在这里插入图片描述
    初始化:
    首先创建n个仅含一个元素的最大HBLT,这n棵树组成一个FIFO队列,然后从队列中依次成对删除HBLT,然后将其合并后再插入队列末尾,知道队列只有一颗HBLT为止。

    4 应用

    堆排序
    机器调度
    霍夫曼编码

    展开全文
  • 数据结构--优先级队列(堆)一级目录二级目录三级目录 一级目录 二级目录 三级目录

    什么是优先级队列

    队列是一种先进先出(FIFO)的数据结构,优先级队列也是一个队列,但并不是单纯的先进先出,而是把优先级最高的先出去,优先级队列内部结构就是堆(Heap)

    常用接口介绍

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

    PriorityQueue特性

    1. 使用时必须导入PriorityQueue所在的包,即:
    import java.util.PriorityQueue;
    
    1. PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出
      ClassCastException异常
    2. 不能插入null对象,否则会抛出NullPointerException
    3. 没有容量限制,可以插入任意多个元素,其内部可以自动扩容
    4. 插入和删除元素的时间复杂度为 O ( l o g 2 N ) O(log_2N) O(log2N)
    5. PriorityQueue底层使用了堆数据结构

    PriorityQueue常用接口介绍

    优先级队列构造

    构造器功能介绍
    PriorityQueue()创建一个空的优先级队列,默认容量是11
    PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列,注意:initialCapacity不能小于1,否则会抛IllegalArgumentException异常
    PriorityQueue(Collection<? extends E> c)用一个集合来创建优先级队列

    插入/删除/获取优先级元素

    函数名功能介绍
    boolean offer(E e)插入元素e,插入成功返回true,如果e对象为空,抛出NullPointerException异常,时间复杂度 O ( l o g 2 N ) O(log_2N) O(log2N),注意:空间不够时候会进行扩容
    E peek()获取优先级最高的元素,如果优先级队列为空,返回null
    E poll()移除优先级最高的元素并返回,如果优先级队列为空,返回null
    int size()获取有效元素的个数
    void clear()清空
    boolean isEmpty()检测优先级队列是否为空,空返回true
    import java.util.PriorityQueue;
    
    public class Test {
        public static void main(String[] args) {
            PriorityQueue<Integer> q = new PriorityQueue<>();
            int [] arr = {9, 5, 2 ,7, 3, 8, 6};
            // 将数组元素插入到队列中
            for (int x : arr) {
                q.offer(x);
            }
            // 获取队列 q 中有效元素个数
            System.out.println(q.size());
            // 获取优先级最高元素
            System.out.println(q.peek());
            // 将优先级最高元素弹出,并返回
            while (! q.isEmpty()) {
                System.out.println(q.poll());
            }
    
            q.offer(0);
            // 清空
            q.clear();
            if (q.isEmpty()) {
                System.out.println("优先级队列 null");
            } else {
                System.out.println("优先级队列 !null");
            }
        }
    }
    

    Comparable 接口

    Comparable接口是 Java 标准库中内置的一个 “接口” interface,里面只有一个抽象方法,comparaTo(Object other),通过这个方法来指定对象自身和另一个对象之间的大小关系。

    java.lang.Comparable;
    

    Comparator接口,也有类似的作用,Comparator接口,哪个类需要比较,就需要让这个类实现该接口。

    优先级队列的应用

    1. 用来排序(堆排序)
    2. 用来排序提取前 k 个元素
    展开全文
  • 栈、队列和优先级队列都是非常基础的数据结构。Python作为一种“编码高效”的语言,对这些基础的数据结构都有比较好的实现。在业务需求开发过程中,不应该重复造轮子,今天就来看看些数据结构都有哪些实现。 0x00 ...
  • 使用数据结构的性能优先级队列实现。 目录 。尺寸() .toArray() 。清除() 建造 执照 安装 npm install --save @datastructures-js/priority-queue 原料药 此存储库中有两种类型的PriorityQueue:...
  • 基础数据结构 队列机构 Queue 先进先出 FIFO(first In First Out) 允许在前端(front)删除,允许在后端(rear)插入 特殊:优先级队列 队列相当于一个集合或者队列,一个任务集合; 特点:先进先出(谁先进来...
  • 数据结构笔记3.4 与普通的队列不同,优先级队列并不一定按照FIFO(先进先出)的原则对数据进行操纵,而是每次从队列取出具有最高优先权的元素。打个比方,你现在有一堆任务,而你只能一项一项的完成,一种方式是哪...
  • 数组实现优先级队列

    2020-09-05 13:34:15
    优先级队列优先级队列中,数据项按...优先级队列通常堆来实现。数组实现优先级队列,插入数据项比较慢。 数组实现优先级队列 package com.dstructure.queue; /** * @ClassName PriorityQueue * @Author gg_gi
  • 数据结构之带优先级队列(C语言实现)
  • 优先级队列通常使用数据结构实现。 在本文中,我们将讨论使用数据结构在python中实现优先级队列的方法。 让我们开始吧! 在构建" PriorityQueue"类之前,值得熟悉python" heapq"模块。 ...
  • 优先级队列
  • 优先级队列(Priority Queues)     优先级队列是存储具有自然顺序的元素的集合。 从优先级队列中删除项目总是产生最小的元素。   A priority queue is a collection that stores elements that ...
  • 优先级队列(priority queue)是0个或多个元素的集合,每个元素都有一个优先权,接下来就来看一下简洁的Python实现优先级队列结构的方法详解:
  • 优先级队列是一种循优先级访问的不失高效的轻量级数据结构优先级队列只需要维持偏序即可满足设计目标。优先级队列实现依托于向量的“肉”和二叉树的“灵”,完全二叉堆与左式堆是优先级队列实现的两种方式。 ...
  • 文章目录一.什么是队列二.队列的封装三、队列的常见的操作3.1 enqueue(element):向队列尾部添加一个新的项3.2 ... 优先级队列的封装5.1概念5.2 封装5.3 添加方法 一.什么是队列 只允许在一端插入数据操作,在另一
  • 优先级队列Java实现

    2020-12-23 12:56:45
    优先级队列也是个队列,因此也是提供以下接口 ◼ int size(); // 元素的数量 ◼ boolean isEmpty(); // 是否为空 ◼ void enQueue(E element); // 入队 ◼ E deQueue(); // 出队 ◼ E front(); // 获取队列的头...
  • 实现优先级队列(Priority Queue)

    千次阅读 2018-04-13 22:52:38
    1.优先级队列定义: 优先级队列(priority queue) 是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找...2.优先级队列实现方案 优先级队列实现既要兼顾成本,也要兼顾效率 ...
  • 优先级队列简介及Python手工实现
  • 本文实例讲述了Python实现数据结构与算法之队列。分享给大家供大家参考。具体分析如下: 一、概述 队列(Queue)是一种先进先出(FIFO)的线性数据结构,插入操作在队尾(rear)进行,删除操作在队首(front)进行...
  • 数据结构课设——小大根交替堆实现的双端优先级队列及应用
  • 优先级队列实现

    2021-04-16 15:48:15
    在Java中,普通队列是由双向链表来实现的,如果优先级队列使用双向链表,那么通过遍历找优先级最高的节点需要O(n)的时间复杂度,但如果使用二叉堆,那么入队和出队的时间复杂度都可以降到O(logn)。 接口 ...
  • 主要介绍了Java数组模拟优先级队列数据结构的实例,优先级队列中的元素会被设置优先权,本文的例子借助了Java中的TreeSet和TreeMap,需要的朋友可以参考下
  • 一、队列 function Queue() { // 创建一个队列的容器 this.container = []; } Queue.prototype = { constructor: Queue, // 进入队列 element进入队列的元素 enter: function enter(element) { this....
  • 数据结构——优先级队列一、什么是优先级队列 一、什么是优先级队列 在了解了什么是队列以后,我们再来了解优先级队列,顾名思义,优先级队列就是在队列的基础上给每个元素加上了先后顺序,我们仍然拿排队买票的例子...
  • 1.优先级队列是什么 2.如何使用优先级队列 3.优先级队列的特性,常用方法 4.自定义优先级队列实现
  • 这种数据结构就是优先级队列(Priority Queue) 优先级队列实现 堆的概念 如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:Ki <= ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 113,086
精华内容 45,234
关键字:

数据结构用队列实现优先级的队列

数据结构 订阅