priority queue（优先队列中的pop函数是将元素删除出来还是放到队尾）

本文目录

• 优先队列中的pop函数是将元素删除出来还是放到队尾
• java 优先队列（priority queue）中，提取第二优先级的值并删除，但是不删除第一优先值的数，怎么实现
• c++ STL求讲解priority_queue, less >
• C语言实现优先队列(priority queue)
• 能不能用哈希表（hash table)实现优先队列（priority queue)
• 什么是优先队列
• 在priority_queue中,如果要自己定义排序规则为什么只能重载<,而不能重载>呢
• 《STL源码分析》中如何priority_queue使用greater函数对象
• python priority queue 怎么得到标签

优先队列中的pop函数是将元素删除出来还是放到队尾

删除元素。

1. 优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,

2. 对优先队列执行的操作有

            1) 查找;

            2) 插入一个新元素;

            3) 删除.

1. 在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;

2. 对于最大优先队列(max priority queue),查找操作用来搜索优先权最大的元素,删除操作用来删除该元素。

3. 由于这是一个queue，所以只允许在底端加入元素，并从顶端取出元素，除此之外别无其它存取元素的途径。

4. priority_queue 带有权值观念，其内的元素并非依照被推入的次序排列，而是自动依照元素的权值排列（通常权值以实值表示）。

java 优先队列（priority queue）中，提取第二优先级的值并删除，但是不删除第一优先值的数，怎么实现

你要的是这样的效果么

public static void main(String args) {
  PriorityQueue《Integer》 pq = new PriorityQueue《Integer》();
  pq.add(5);
  pq.add(2);
  pq.add(3);
  pq.add(4);
  System.out.println("取出了"+pq.poll()+",队列剩余"+Arrays.toString(pq.toArray()));
  
  /**
   * 假设3是我不满意的值，我要取到3后面的值
   */
  if(pq.peek()==3){
   System.out.println("3真不是我想要的，我可以接着往下处理么?ok,将3先保留吧");
   int a = pq.poll();//将当前的第一级优先的值暂存下来，等第二级优先的值取出后再将其加入
   pq.poll();
   pq.add(a);
   System.out.println("队列剩余"+Arrays.toString(pq.toArray()));
  }
  
  System.out.println("取出了"+pq.poll()+",队列剩余"+Arrays.toString(pq.toArray())); 
  
 }

打印效果:

取出了2,队列剩余
3真不是我想要的，我可以接着往下处理么?ok,将3先保留吧
队列剩余
取出了3,队列剩余

我觉得这个是优先队列，虽然poll时候会将优先级高的数据先取出，但是同样的，如果加进去是高优先级的数据 下次取的时候它依然还是高优先级的数据。

c++ STL求讲解priority_queue, less >

priority_queue是一个顺序容器适配器，其原型：
template 《class T, class Container = vector《T》,
class Compare = less《typename Container::value_type》 》 class priority_queue;
可见第二个vector《int》是其Container，即优先队列的基础容器是vector《int》，优先队列在vector《int》这一容器类型基础上实现。

C语言实现优先队列(priority queue)

        堆排序是一个比较优秀的算法,堆这种数据结构在现实生活中有很多的应用,比如堆可以作为一个优先队列来使用,作为一个高效的优先队列,它与堆的结构一样,都有最大优先队列,最小优先队列.优先队列priority queue 是一种用来维护一组元素构成的集合S的数据结构，每一个元素都有一个相关的值，称为关键字（key）。

        最大优先队列包含以下操作：

         将元素x插入到S的集合中，等价于 ；

         返回S中最大元素；

         返回并且删除S中最大元素；

         将元素x的关键字增加到key，要求 。

        同样的，最小优先队列操作也包括： , , , 。只不过是对最小值进行操作。

        在这里主要讨论最大优先队列，其应用很多，在共享计算机作业系统就是，类似于早期的unix主机，管理员root可以设置n个不同的用户，以及各个用户不同的操作权限，从主机那里接出多个终端，每个操作人员（程序员）在自己的工作终端 ，感觉像是自己拥有自己独立的作业主机一样，其实不是，通过一些任务调度来实现，其中就有任务等待执行相关队列，并且有各个任务有着自己优先级，以便确定调度执行具体任务，如果你学过操作系统相关知识，那么应该对系统调度有所了解。

        当一个作业被完成或者被中断后，调度器会调用 来调用所有在队列中等待任务中优先级最高的任务执行，在新任务加入等待任务时会调用 加入任务等待队列，当某个任务等待时间过长时可通过 提高其优先级，从而减少等待时间。

        下面是具体实现C程序源码：

#include 《stdio.h》

#define NAGE_INFINIT -99999

#define parent(i) i/2

#define left(i) 2*i+1

#define right(i) 2*i+2

//get array of A first element

int heap_maximum(int A;}

/***********************************************

*

* function max_heapify();

*

* args

*  A inttype save elements of heap

*  i index of A

*  heap_size real length of A

*

* ********************************************/

void max_heapify(int A,int i,int heap_size){

    int l,r,largest,temp;

    l=left(i);

    r=right(i);

    if((l《=heap_size)&&(A))

        largest=l;

    else

        largest=i;

    if((r《=heap_size)&&(A))

        largest=r;

    if(largest!=i){

        temp=A;

        A;

        A=temp;

        max_heapify(A,largest,heap_size);

    }

}

/*********************************************

*

* function heap_extract_max()

*

* args

*  A inttype save elements of heap

*  heap_size inttype the real length of A

*

* return max the parent node value

*

* ******************************************/

int heap_extract_max(int A,int heap_size){

    int max;

    if(heap_size《0)

        return -1;  //heap underflow

    max=A;  //parent node the max value of element

    A;

    heap_size--;

    /**************************************

    * dajust binary heap(or tree) to make

    * sure heap fo A true every times

    *

    * ************************************/

    max_heapify(A,0,heap_size);

    return max;

}

/***********************************************

*

* function heap_increase_key();

*

* args

*  A inttype save elemnts of heap

*  i index of A

*  key inserted element

*

* *********************************************/

void heap_increase_key(int A,int i,int key){

    int temp;

    if(key《A){

        printf("new key is **aller than current key\n");

        return;    //over programming

    }

    A=key;

    //p=parent(i);

    while ((i》0)&&(A)) {

        temp=A;

        A;

        A=temp;

        i=parent(i); //update index of A

        //p=parent(i);

    }

}

/***************************************************

*

* function max_heap_insert();

*

* args

*  A inttype save elements of A

*  key inserted element to A

*  heap_size real length of A

*

* **************************************************/

void max_heap_insert(int A,int key,int heap_size){

    heap_size+=1;

    A=NAGE_INFINIT;

    heap_increase_key(A,heap_size,key);

}

int main()

{

    int heap_max,max,i,key;

    int A;

    int heap_size=0;

    char c;

    while (1) {

        scanf("%d",&A);

        c=getchar();

        if(c==’\n’)

            break;

        heap_size++;

    }

    //copy A to Temp

    for(i=0;i《=heap_size;i++)

        Temp;

    //get heap maximum element

    heap_max=heap_maximum(A);

    printf("heap of A maximum element: %d\n",heap_max);

    //copy Temp to A

    for(i=0;i《=heap_size;i++)

        A;

    /*--extract maximum element--*/

    max=heap_extract_max(A,heap_size);

    printf("extract element: %d \n",max);

    printf("new heap of A after extract maximum node\n");

    for(i=0;i《heap_size;i++)

        printf("%d ",A);

    printf("\n");  //next line

    //copy Temp to A

    for(i=0;i《=heap_size;i++)

        A;

    /*--increase from A to key--*/

    printf("input i key ");

    scanf("%d %d",&i,&key);

    heap_increase_key(A,i,key);

    for(i=0;i《=heap_size;i++)

        printf("%d ",A);

    printf("\n");

    //copy Temp to A

    for(i=0;i《=heap_size;i++)

        A;

    /*--insert queueu--*/

    key=0;  //init key;

    printf("input key: ");

    scanf("%d",&key);

    max_heap_insert(A,key,heap_size);

    for(i=0;i《=heap_size+1;i++)

        printf("%d ",A);

    printf("\n");

    return 0;

}

/****************************************

*

* input 16 14 10 8 7 9 3 2 4 1

*      i: 8

*      key: 15

*

* output in function main()

* **************************************/

其运行结果如下图：
欢迎留言交流，也感谢指正，一起进步。

能不能用哈希表（hash table)实现优先队列（priority queue)

不行，hash table里面的元素是无序的。

Hash表本来就是按照内容存储，可以在确定散列函数的时候考虑优先级，一个思路是先将元素按优先级排序，根据散列函数自变量是优先级，按数值大小对应过去。

哈希表是不可以排序的，你可以查查哈希表的作用，概念等，哈希表是为了查找方便而设计的一种数据结构，它的排列是按照哈希函数计算得出的。具体内部的运行机制我也不知道。

扩展资料：

若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。

对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。

综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。

什么是优先队列

优先队列(priority queue)普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高进先出 （largest-in，first-out）的行为特征。

在priority_queue中,如果要自己定义排序规则为什么只能重载<,而不能重载>呢

stl中有关排序的容器类都有一个表示排序规则的对象的，优先队列的定义大致是这样的：
template《typename _Tp, typename _Sequence = vector《_Tp》, typename _Compare = less《typename _Sequence::value_type》 》 class priority_queue { …… };
其中模板类型的一个参数_Tp是容器装的类型，第二个是他包装的类型，和这个问题无关，第三个_Compare就是比较器，默认是std::less，也就是小于号，你完全可以传一个自定义的对象进去，当然也可以用stl帮你定义好的，比如greater, 像下面这样写的话，整个排序就倒过来了，因为用的是大于号
priority_queue《int, vector《int》, std::greater《int》 》 q;

《STL源码分析》中如何priority_queue使用greater函数对象

首先查看手册，priority_queue的定义如下：

template《class T, class Container = std::vector《T》, class Compare = std::less《typename Container::value_type》》 class priority_queue;

然后继续看模板的三个参数的说明

—————————以下直接摘抄的—————

Template parameters

T    -    The type of the stored elements. The behavior is undefined if T is not the same type asContainer::value_type. (since C++17)    

Container    -    The type of the underlying container to use to store the elements. The container must satisfy the requirements of SequenceContainer, and its iterators must satisfy the requirements of LegacyRandomAccessIterator. Additionally, it must provide the following functi*** with the usual semantics:

• front()

• push_back()

• pop_back()

The standard containers std::vector and std::deque satisfy these requirements.

Compare    -    A Compare type providing a strict weak ordering.    

—————————以上直接摘抄的—————

故可知，使用priority_queue需要给三个类来实现模板，其中第三个类就是那个比较函数，你问的，为什么要priority_queue《int, vector《int》, greater《int》 》 q1;已经回答完毕。

另外，可以参考std::less的定义，更深入学习第三个类的含义。已附在引用部分，自行查阅。

std::priority_queue std::less

PS：第一个那家伙回答的什么东西！我本来是不想回答的。。。看见那家伙胡诌一气，气不过。

python priority queue 怎么得到标签

Queue
Queue是python标准库中的线程安全的队列（FIFO）实现,提供了一个适用于多线程编程的先进先出的数据结构，即队列，用来在生产者和消费者线程之间的信息传递
基本FIFO队列
class Queue.Queue(maxsize=0)
FIFO即First in First
Out,先进先出。Queue提供了一个基本的FIFO容器，使用方法很简单,maxsize是个整数，指明了队列中能存放的数据个数的上限。一旦达到上
限，插入会导致阻塞，直到队列中的数据被消费掉。如果maxsize小于或者等于0，队列大小没有限制。
举个栗子：
import Queue
q = Queue.Queue()
for i in range(5):
q.put(i)
while not q.empty():
print q.get()
输出：
0
1
2
3
4
LIFO队列
class Queue.LifoQueue(maxsize=0)
LIFO即Last in First Out,后进先出。与栈的类似，使用也很简单,maxsize用法同上
再举个栗子：
import Queue
q = Queue.LifoQueue()
for i in range(5):
q.put(i)
while not q.empty():
print q.get()
输出：
4
3
2
1
0
可以看到仅仅是将Queue.Quenu类替换为Queue.LifiQueue类
优先级队列
class Queue.PriorityQueue(maxsize=0)
构造一个优先队列。maxsize用法同上。
import Queue
import threading
class Job(object):
def __init__(self, priority, description):
self.priority = priority
self.description = description
print ’Job:’,description
return
def __cmp__(self, other):
return cmp(self.priority, other.priority)
q = Queue.PriorityQueue()
q.put(Job(3, ’level 3 job’))
q.put(Job(10, ’level 10 job’))
q.put(Job(1, ’level 1 job’))
def process_job(q):
while True:
next_job = q.get()
print ’for:’, next_job.description
q.task_done()
workers = [threading.Thread(target=process_job, args=(q,)),
threading.Thread(target=process_job, args=(q,))
]
for w in workers:
w.setDaemon(True)
w.start()
q.join()
结果
Job: level 3 job
Job: level 10 job
Job: level 1 job
for: level 1 job
for: level 3 job
for: job: level 10 job
一些常用方法
task_done()
意味着之前入队的一个任务已经完成。由队列的消费者线程调用。每一个get()调用得到一个任务，接下来的task_done()调用告诉队列该任务已经处理完毕。
如果当前一个join()正在阻塞，它将在队列中的所有任务都处理完时恢复执行（即每一个由put()调用入队的任务都有一个对应的task_done()调用）。
join()
阻塞调用线程，直到队列中的所有任务被处理掉。
只要有数据被加入队列，未完成的任务数就会增加。当消费者线程调用task_done()（意味着有消费者取得任务并完成任务），未完成的任务数就会减少。当未完成的任务数降到0，join()解除阻塞。
put(item)
将item放入队列中。
如果可选的参数block为True且timeout为空对象（默认的情况，阻塞调用，无超时）。
如果timeout是个正整数，阻塞调用进程最多timeout秒，如果一直无空空间可用，抛出Full异常（带超时的阻塞调用）。
如果block为False，如果有空闲空间可用将数据放入队列，否则立即抛出Full异常
其非阻塞版本为put_nowait等同于put(item, False)
get()
从队列中移除并返回一个数据。block跟timeout参数同put方法
其非阻塞方法为｀get_nowait()｀相当与get(False)
empty()
如果队列为空，返回True,反之返回False