精华内容
下载资源
问答
  • //创建优先队列的三种最基本方式 priority_queue<int> q;//默认按照升序 priority_queue<int,vector<int>,greater<int> > q2;//从...
    #include<bits/stdc++.h>
    using namespace std;
    int main(){
        //创建优先队列的三种最基本方式
        priority_queue<int> q;//默认按照升序
        priority_queue<int,vector<int>,greater<int> > q2;//从小到大
        priority_queue<int,vector<int>,less<int> > q3;//从大到小
        //本质使队列
        //插入,删除,清空,访问,与队列相同
        q.push(5);q.push(6);//插入的数据可以相同,优先队列的优点在于自动调整顺序
        q.pop();//删除堆顶
        while(!q.empty())   {cout<<q.top()<<endl;   q.pop(); } //遍历
        //清空操作
        while(!q.empty()) q.pop();
        return 0;
    }
    

     

    展开全文
  • 简单介绍C++STL中优先队列的使用,对应举几个简单的例子帮助大家了解使用。

    C++STL中非常有用的一中数据结构就是队列,其中一种很常用的队列是优先队列。优先队列是按找一定排序方式将push进去的元素进行排列。

    默认排序方式是大顶堆,即值大的在队首,从大到小出队。

    priority_queue<int> myQ;
    	myQ.push(1);
    	myQ.push(2);
    	myQ.push(3);
    	myQ.push(4);
    	myQ.push(5);
    	cout<<myQ.top()<<endl;
    	//输出5
    

    还可以从小到大出队,就是小顶堆,不过需要显示改变它的排序方式

    	priority_queue<int,vector<int>,greater<int> > myQ;
    	myQ.push(1);
    	myQ.push(2);
    	myQ.push(3);
    	myQ.push(4);
    	myQ.push(5);
    	cout<<myQ.top()<<endl;
    	//输出1
    

    自定义排序

    下面就简单写一下我们自己实现大顶堆的排序的方法。

    
    struct cmp{ 
     
        bool operator()( const int& a , const int& b )const{ 
     
            return a < b ;      //大顶堆 
     
        } 
     
    }; 
    	priority_queue<int, vector<int>,cmp> myQ;
    	myQ.push(1);
    	myQ.push(2);
    	myQ.push(3);
    	myQ.push(4);
    	myQ.push(5);
    	cout<<myQ.top()<<endl;
    	//输出5
    
    

    自定义排序方式同样适用于各种数据类型和自定义结构体。

    注意:如果自定义排序方式,第二个参数千万不要省略,虽然第二个参数对我们没什么用,但优先队列实际上底层实现的时候需要,所以需要写。
    当不需要自定义排序的话,后两个参数可以省略。

    展开全文
  • 优先队列入队操作

    2019-08-31 15:19:08
    注意:这里描述的是优先队列入队操作 , 入队使用 shiftUp ,出队使用 shiftDown ,只要在末尾添加一个元素,就对这最后一个元素执行shiftUp操作 public class Main { public static void main(String[] ...

    效果展示:
    在这里插入图片描述
    这里我们从数组的一号位置开始存储
    那么在二叉树中的规律是
    parent(i) = i/2;
    leftChild of (i) = 2i;
    rightChild of (i) = 2
    i+1;

    在这里插入图片描述
    如上图所示,我们发现,连线的间隔越是往后,距离就越大,而且正好是2的倍数,间隔呈现2,4,8那样增长

    由于 parent(i) = i/2 ,如上图所示, 15位置是 10 ,那么他的父亲节点位置是 5,也就是41,41的位置是5,那么他父亲节点的位置是2,(这里我没有写 0号元素),也就是52
    我们会发现,每一次找父节点都是 当前节点的位置除以2,也就是相当于折半查找。我们知道

    2的19次方524 288 ,也就是说第524288位元素,他最多有19个祖宗,也就是说只要查找19次,就跳到了数组的头部
    维持这个大根堆,我们使用 shiftUp 操作,i节点第(i/2)位节点(他爸爸)比较,如果i比 他父亲
    要大,就互换,维持大的在上面,小的在下面的结构,这里就有点像冒泡排序那样的交换排序,只要大就交换,不过冒泡是大的放后面

    注意:这里描述的是优先队列的入队操作入队使用 shiftUp,出队使用 shiftDown,只要在末尾添加一个元素,就对这最后一个元素执行shiftUp操作

    public class Main {
    
    
        public static void main(String[] args) {
    
            
            Random r = new Random();
            MaxHeap  p = new MaxHeap(100);
            int n = 50;
            int m =100;
            for(int i=0;i<n;++i) {
                int t = r.nextInt(100);
                p.insert(t);
    
            }
    
            p.treePrint();
    
    
        }
    
    
    
    
    
    }
    
    
    
    
    
    class MaxHeap {
        int[] data;
        int count;
        int capacity;
    
        public MaxHeap(int capacity) {
            this.capacity = capacity;
            data = new int[capacity];
            this.count=0;
    
        }
        int size() {
            return count;
        }
    
        public boolean isEmpty() {
            return count==0;
        }
        void insert(int e) {
            data[count+1]=e;
            count++;
            shiftUp(count);
        }
    
        void swap(int i,int j) {
            if(data[i]==data[j])return;
            data[i]^=data[j];
            data[j]^=data[i];
            data[i]^=data[j];
        }
    
        void shiftUp(int k) {
            while (k>1&&data[k]>data[k/2])
            {
                swap(k,k/2);
                k/=2;
            }
        }
    
    
    
    
        public void treePrint() {
    
            // 最多打印100个元素
            if (size() >= 100) {
                System.out.println("This print function can only work for less than 100 integer");
                return;
            }
    
            System.out.println("The max heap size is: " + size());
            System.out.println("Data in the max heap: ");
            for (int i = 0; i < size(); i++) {
                // 我们的print函数要求堆中的所有整数在[0, 100]的范围内
                assert (Integer) data[i] >= 0 && (Integer) data[i] < 100;
                System.out.println(data[i] + " ");
            }
    
            System.out.println();
            System.out.println();
    
            int n = size();
            int maxLevel = 0;
            int numberPerLevel = 1;
            while (n > 0) {
                maxLevel += 1;
                n -= numberPerLevel;
                numberPerLevel *= 2;
            }
    
            int maxLevelNumber = (int) Math.pow(2, maxLevel - 1);
            int curTreeMaxLevelNumber = maxLevelNumber;
            int index = 1;
            for (int level = 0; level < maxLevel; level++) {
    
                String line1 = new String(new char[maxLevelNumber * 3 - 1]).replace('\0', ' ');
    
                int curLevelNumber = Math.min(count - (int) Math.pow(2, level) + 1, (int) Math.pow(2, level));
                boolean isLeft = true;
                for (int indexCurLevel = 0; indexCurLevel < curLevelNumber; index++, indexCurLevel++) {
                    line1 = putNumberInLine((Integer) data[index], line1, indexCurLevel, curTreeMaxLevelNumber * 3 - 1, isLeft);
                    isLeft = !isLeft;
                }
                System.out.println(line1);
    
                if (level == maxLevel - 1) {
                    break;
                }
    
                String line2 = new String(new char[maxLevelNumber * 3 - 1]).replace('\0', ' ');
                for (int indexCurLevel = 0; indexCurLevel < curLevelNumber; indexCurLevel++) {
                    line2 = putBranchInLine(line2, indexCurLevel, curTreeMaxLevelNumber * 3 - 1);
                }
                System.out.println(line2);
    
                curTreeMaxLevelNumber /= 2;
            }
        }
    
    
        private String putNumberInLine(Integer num, String line, int indexCurLevel, int curTreeWidth, boolean isLeft) {
    
            int subTreeWidth = (curTreeWidth - 1) / 2;
            int offset = indexCurLevel * (curTreeWidth + 1) + subTreeWidth;
            assert offset + 1 < line.length();
            if (num >= 10) {
                line = line.substring(0, offset + 0) + num.toString()
                        + line.substring(offset + 2);
            } else {
                if (isLeft) {
                    line = line.substring(0, offset + 0) + num.toString()
                            + line.substring(offset + 1);
                } else {
                    line = line.substring(0, offset + 1) + num.toString()
                            + line.substring(offset + 2);
                }
            }
            return line;
        }
    
        private String putBranchInLine(String line, int indexCurLevel, int curTreeWidth) {
    
            int subTreeWidth = (curTreeWidth - 1) / 2;
            int subSubTreeWidth = (subTreeWidth - 1) / 2;
            int offsetLeft = indexCurLevel * (curTreeWidth + 1) + subSubTreeWidth;
            assert offsetLeft + 1 < line.length();
            int offsetRight = indexCurLevel * (curTreeWidth + 1) + subTreeWidth + 1 + subSubTreeWidth;
            assert offsetRight < line.length();
    
            line = line.substring(0, offsetLeft + 1) + "/" + line.substring(offsetLeft + 2);
            line = line.substring(0, offsetRight) + "\\" + line.substring(offsetRight + 1);
    
            return line;
        }
    
    
    
    
    
    }
    
    
    
    展开全文
  • 优先队列的实现

    2019-12-04 21:11:46
    1.“上浮”操作(用于优先队列入队) 2.“下沉”操作(用于优先队列出队) 3.完整代码 一、什么是优先队列? 我们知道队列的特点是先进先出(FIFO),第一个进队列的元素最先出队,而优先队列的出队顺序,不是按...

    在我的上一篇文章(二叉堆的节点插入、删除以及构建过程)中,介绍了二叉堆,包括最大堆和最小堆,优先队列正是基于二叉堆来实现的。

    目录

    一、什么是优先队列?

    二、优先队列的实现

    1.“上浮”操作(用于优先队列入队)

    2.“下沉”操作(用于优先队列出队)

    3.完整代码


    一、什么是优先队列?

    我们知道队列的特点是先进先出(FIFO),第一个进队列的元素最先出队,而优先队列的出队顺序,不是按照入队顺序来排序的。

    • 在一个最大优先队列中,无论入队顺序如何,都是当前最大的元素优先出队。
    • 在一个最小优先队列中,无论入队顺序如何,都是当前最小的元素优先出队。

    当然,我们可以用线性的数据结构来实现最大优先队列和最小优先队列,但是算法的时间复杂度会比较高O(n)。

    二、优先队列的实现

    若我们采用最大堆来实现最大优先队列,栈顶元素就是最大元素,那么每次入队时,都将元素插在二叉堆最后一个位置,然后进行“上浮”操作(此时是将较大的值往上移);在出队时,即是删除堆顶节点,然后将最后一个节点替换到堆顶位置,再进行该节点的“下沉”操作(此时是将较小的值往下移,同样理解为大值上移)。

    因为上浮操作和下沉操作的时间复杂度是O(logn),所以优先队列的入队和出队的时间复杂度也是O(logn)。

    先说明一点:构建最大优先队列或者最小优先队列的区别,只是在入队和出队时,“上浮”和“下沉”操作中,变换判断的符号即可。 

    1.“上浮”操作(用于优先队列入队)

    在最大优先队列(对应于最大堆,父节点值大于左右孩子节点)入队时,因为插入的位置在二叉堆的最后位置,若该元素为较大的元素,则需要将该节点进行“上浮”。

    “上浮”操作(构建最大堆)的思路:

    用childIndex来记录插入的节点位置,用temp值记录需要“上浮”的节点值,将childIndex的值与父节点的值进行比较,若孩子节点的值大于父节点,则进行“上浮”操作:单向赋值(无需实际交换两个值),将父节点值赋给孩子节点,然后将孩子节点指针指向父节点,并重新计算父节点指针。若一直上浮到根节点,此时childIndex=0,那么直接将temp值赋值给根节点,因此循环判断的条件中要加上childIndex > 0.具体的实现为:

    //实现一个最大堆
        public void upAdjust(){
            int childIndex = size - 1;
            int parentIndex = (childIndex - 1) / 2;
            int temp = array[childIndex];
            while(childIndex > 0 && temp > array[parentIndex]){//若后一个大于号改为小于号,则是最小堆
                array[childIndex] = array[parentIndex];
                childIndex = parentIndex;
                parentIndex = (childIndex - 1) / 2;
            }
            array[childIndex] = temp;
        }

    2.“下沉”操作(用于优先队列出队)

    在最大优先队列(对应于最大堆)出队时,我们移除堆顶节点,同时将最后一个节点替换堆顶节点,此时需要进行“下沉”操作。

    “下沉”操作(构建最大堆)的思路:

    用childIndex来记录左右孩子中较大的那个,然后将父节点与该孩子节点进行比较,若孩子节点值大于父节点,则进行“下沉”操作,同样是单向赋值,循环的条件为childIndex < size(数组长度),当父节点值大于等于孩子节点时,退出循环。具体实现为:

    public void downAdjust(){
            int parentIndex = 0;
            int childIndex = 1;
            int temp = array[parentIndex];
            while(childIndex < size){
                if(childIndex + 1 < size && array[childIndex+1] > array[childIndex]){//若构建最小堆将后一个大于号改为小于号
                    childIndex++;
                }
                if(array[parentIndex] >= array[childIndex])//若构建最小堆将大于等于改为小于等于
                    break;
                array[parentIndex] = array[childIndex];
                parentIndex = childIndex;
                childIndex = 2 * parentIndex + 1;
            }
            array[parentIndex] = temp;//此处一定是parentIndex,因为childIndex可能已经超尺寸了
        }

    3.完整代码

    下面以最大优先队列的入队和出队为例,给出完整的代码实现。

    import java.util.Arrays;
    
    public class PriorityQueue {
        private int[] array;
        private int size;
        public PriorityQueue(){
            array = new int[32];
        }
    
        //入队(最大优先队列)
        public void enQueue(int key){
            if(size >= array.length)
                resize();
            array[size++] = key;
            upAdjust();//实现最小优先队列,这里将upAjust()改为upAdjust1()即可
        }
    
        //出队(最大优先队列)
        public int deQueue() throws Exception {
            if(size <= 0)
                throw new Exception("队列为空,不能出队!");
            int head = array[0];
            array[0] = array[--size];
            downAdjust();//实现最小优先队列,这里将downAjust()改为downAdjust1()即可
            return head;
        }
    
        //实现一个最大堆
        public void upAdjust(){
            int childIndex = size - 1;
            int parentIndex = (childIndex - 1) / 2;
            int temp = array[childIndex];
            while(childIndex > 0 && temp > array[parentIndex]){
                array[childIndex] = array[parentIndex];
                childIndex = parentIndex;
                parentIndex = (childIndex - 1) / 2;
            }
            array[childIndex] = temp;
        }
    
        //实现一个最小堆,只需要将判断条件中的大于号改为小于号即可
        public void upAdjust1(){
            int childIndex = size - 1;
            int parentIndex = (childIndex - 1) / 2;
            int temp = array[childIndex];
            while(childIndex > 0 && temp < array[parentIndex]){
                array[childIndex] = array[parentIndex];
                childIndex = parentIndex;
                parentIndex = (childIndex - 1) / 2;
            }
            array[childIndex] = temp;
        }
    
        //实现一个最大堆
        public void downAdjust(){
            int parentIndex = 0;
            int childIndex = 1;
            int temp = array[parentIndex];
            while(childIndex < size){
                if(childIndex + 1 < size && array[childIndex+1] > array[childIndex]){//最大堆中左右孩子节点取较大的那个进行移动
                    childIndex++;
                }
                if(array[parentIndex] >= array[childIndex])
                    break;
                array[parentIndex] = array[childIndex];
                parentIndex = childIndex;
                childIndex = 2 * parentIndex + 1;
            }
            array[parentIndex] = temp;//此处一定是parentIndex,因为childIndex可能已经超尺寸了
        }
    
        //实现一个最小堆
        public void downAdjust1(){
            int parentIndex = 0;
            int childIndex = 1;
            int temp = array[parentIndex];
            while(childIndex < size){
                if(childIndex + 1 < size && array[childIndex+1] < array[childIndex]){//最小堆中左右孩子节点取较小的那个进行移动
                    childIndex++;
                }
                if(temp <= array[childIndex])
                    break;
                array[parentIndex] = array[childIndex];
                parentIndex = childIndex;
                childIndex = 2 * parentIndex + 1;
            }
            array[parentIndex] = temp;//此处一定是parentIndex,因为childIndex可能已经超尺寸了
        }
    
        public void resize(){
            int newLength = array.length * 2;
            this.array = Arrays.copyOf(this.array,newLength);//剩余长度用0补齐
        }
    
        public static void main(String[] args) throws Exception{
            PriorityQueue priorityQueue = new PriorityQueue();
            priorityQueue.enQueue(3);
            priorityQueue.enQueue(5);
            priorityQueue.enQueue(10);
            priorityQueue.enQueue(2);
            priorityQueue.enQueue(7);
            System.out.println("出队元素: "+priorityQueue.deQueue());
            System.out.println("出队元素: "+priorityQueue.deQueue());
        }
    }
    

    运行的结果为:

    出队元素: 10
    出队元素: 7

    展开全文
  • 优先队列自动排序

    千次阅读 2015-01-29 17:23:09
    优先队列自动从从小到大排序,我也是看不懂啊  题目描述 Description  在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。  每一次合并...
  • java 优先队列_优先队列Java

    千次阅读 2020-07-14 02:34:52
    java 优先队列Every now and then we need to process items of a queue in a particular order. Priority queue is a Data Structure that does the job. Java priority queue is different from “normal” queue....
  • 优先队列的出队操作

    2019-08-31 16:00:05
    上一篇文章中我写了优先队列入队操作,入队shiftUp,出队shiftDown 看代码效果: 首先,在优先队列插入50个元素,执行poll操作,也就是出队 把队顶的一个元素拿出 如图,2个97只剩下一个 对于一个50个...
  • 优先队列的学习笔记
  • 详解优先队列

    2019-08-02 00:15:39
    一、队列与优先队列的区别 1、队列是一种FIFO(First-in-Firse-out)先进先出的数据结构,对应生活中排队场景,排在前面的人总是先通过,依次进行。 2、优先队列是特殊的队列,优先一词,就可以看出有插队的现象...
  • 优先队列(priority queue) 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 ...
  • 队列 顺序实现 #define MaxSize 10 typedef struct{ ElemType data[MaxSize];...循环队列——入队 bool EnQueue(SqQueue &Q,ElemType x){ if((Q.rear+1)%MaxSize==Q.front){//队满 return false; } Q.data[Q.r
  • C++中优先队列priority_queue的基础用法

    千次阅读 多人点赞 2020-09-12 17:28:51
    学习优先队列之前先看个单词队列 queue, 这个单词的读法很多人都能独对吧,音标是 `/kjuː/` ,再看一个双端队列 deque,它的音标是 `/dek/`,应该有人读错了吧,反正我是没读对,刚开始看见一次错一次,现在还好了...
  • 队列入队、出队算法

    千次阅读 2019-11-25 23:45:03
    if(Q->front == Q->rear) //空队列 exit(1); p = (*Q).front->next; //删除p结点(队头),Q->front不作为删除对象 e = p->data; (*Q).front->next = p->next; if((*Q).rear == p) (*Q).rear = (*Q).front...
  • 优先队列和堆常用语辅助实现其它算法,例如数据压缩赫夫曼编码算法、Dijkstra最短路径算法、Prim最短生成树算法,优先队列还可以实现事件模拟、选择问题,操作系统的线程调度也使用优先队列优先队列 特点:元素...
  • Java中的优先队列是一种特殊类型的队列,其中所有的元素在创建时都以其自然序或者提供的自定义的Comparator排序。 优先队列的队头包含最小序的元素(根据指定的排序规则),而队尾包含最大序的元素。 因此,当你从...
  • 优先队列算法( Priority queue)前言:源码阅读Priority queue类:底层分析:依据优先级构造堆复杂度分析:Lambda表达式构建Priority queue例题实现: 前言: 引入:优先队列问题常用于降低时间复杂度,达到快速...
  • 优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用堆数据结构来实现。 1、前言 .NET出现20年了,还没有正式...
  • priority_queue 优先级队列,鄙人以为这是一...priority_queue 介绍priority_queue 优先队列的核心操作是支持在常量时间内获得最优先的元素。priority_queue 的难点就在于如何构造优先队列,更具体的说是如何使用自己...
  • Java优先队列PriorityQueue使用详解

    千次阅读 2020-12-01 11:04:40
    一、优先队列概述  简介: API描述: 二、常用方法 构造方法: 方法摘要: 三、优先队列的使用 1.队列保存的是基本数据类型的包装类 2.队列保存的是自定义类 3.优先队列遍历 4.比较器生降序说明 一...
  • 堆实现优先队列

    2019-10-26 21:12:51
    在前面讲了用链队实现优先队列,其思想是插入元素时按普通队列入队,在删除元素(出队)时按优先队列的性质删除.那么就还有一种方式,即插入元素时按优先队列的方式插入,删除时按普通顺序队列的方式删除.那就是用堆实现...
  • 优先队列——C语言实现

    千次阅读 2018-08-25 17:46:18
    优先队列的特点是,进来的,根据优先次序,一个个出来。我们可以使用堆的思想来解决这个问题。 代码: 堆的实现参照:堆——用C语言实现,里面会用到 头文件(包含堆): #define _CRT_SECURE_NO_WARNINGS 1 #...
  • 实现了优先队列的添加与删除方法 优先队列利用最小堆来实现 主要方法:删除堆顶元素、添加元素后最小堆的维护 代码实现 package basicKnowledge.集合框架.priorQueue; import basicKnowledge.集合框架.queue....
  • size() 返回优先队列中拥有的元素个数 top() 返回优先队列对顶元素 在默认的优先队列中,优先级高的先出队。在默认的int型中先出队的为较大的数。 使用方法: 头文件: #include <queue> 声明...
  • Java 优先队列

    千次阅读 2016-05-15 09:29:41
    Java PriorityQueue优先队列是一种重要的数据结构,其利用的是小/大顶堆来实现的。Java中提供了PriorityQueue,PriorityQueue是基于小顶堆实现的无界优先队列,这个优先队列中的元素可以默认自然排序(实现了...
  • 优先队列优化的Dijkstra 1找到最短距离已经确认的顶点,从它出发更新相邻顶点的最短距离 2此后不需要关心1中的“最短距离已经确认的顶点” 堆中元素共有O(V)个,更新和取出都有O(E)次,每次更新或取出堆的维护...
  • 在我们的日常生活中,有许多排队的情形,像在食堂排队打饭,在购票窗口排队购票等等,像这种满足成员元素先进先出特性的问题可以抽象成队列问题(不考虑队尾或者队伍中间的人由于种种因素中途离开的情形),那么什么...
  • 其实实现队列蛮简单的,但敌不过人懒~ 于是stl库中就有了专门实现队列的函数#include<queue> 这里讲解下queue常用的几个操作 1.q.push(),向队列中插入元素 2.q.size(),计算并返回队列大小(也就是队列中...
  • 队列 队列是一种先进先出(First-In-First-Out,FIFO)的数据结构。可以联想一下小朋友排队打疫苗, 排在前头的先打, 排在后边的后打。打完疫苗的朋友就可以回家了(出队),刚到的朋友需要排队(入队)。 1. 实现...
  • PriorityQueue 优先队列 基于MaxHeap最大堆 文章目录1、什么是优先队列2、什么是二叉堆2.1、实现方法2.2、初始化操作2.3、添加元素2.4、提取最大值2.5 查询操作2.6、replace操作2.7、Heapify数组堆化3、优先...
  • 优先队列与最大堆

    2018-07-30 21:32:42
    优先队列:出队顺序与入队顺序无关,和优先级有关 普通队列:先进先出,后进后出 不同底层结构底层实现优先队列的时间 底层机构 入队 出队(拿出最大元素) 普通线性结构 O(1) O(n) 顺序线性...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,868
精华内容 9,547
关键字:

优先队列入队