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

本文目录

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

在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;

什么是优先队列

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

《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 functions 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：第一个那家伙回答的什么东西！我本来是不想回答的。。。看见那家伙胡诌一气，气不过。

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时候会将优先级高的数据先取出，但是同样的，如果加进去是高优先级的数据 下次取的时候它依然还是高优先级的数据。

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

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

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

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

扩展资料：

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

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

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

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》这一容器类型基础上实现。