B*******1
发帖数: 2454 | 1 priority queue 默认就是max heap，但是它的compare函数默认是less的
根据compare class的描述：
Compare: Comparison class: A class such that the expression comp(a,b), where
comp is an object of this class and a and b are elements of the container,
returns true if a is to be placed earlier than b in a strict weak ordering
operation.
如果有a,b, a< b， 那么comp(a,b)就会return true，那么a应该放在b之前阿，但是
为什么会相反的呢？ | y*******g
发帖数: 6599 | 2 compare的描述就是说的less啊
where
,
【在 B*******1 的大作中提到】
: priority queue 默认就是max heap，但是它的compare函数默认是less的
: 根据compare class的描述：
: Compare: Comparison class: A class such that the expression comp(a,b), where
: comp is an object of this class and a and b are elements of the container,
: returns true if a is to be placed earlier than b in a strict weak ordering
: operation.
: 如果有a,b, a< b， 那么comp(a,b)就会return true，那么a应该放在b之前阿，但是
: 为什么会相反的呢？
| B*******1
发帖数: 2454 | 3 为什么呢？
compare 如果是true的话，a就排在b之前
那么less 的话，a < b就是true了
但是默认是max heap
如果push 0 - 20 进去
queue 里面是20 19......
【在 y*******g 的大作中提到】
: compare的描述就是说的less啊
:
: where
: ,
| t****t
发帖数: 6806 | 4 compare class里说的a在b之前, 和priority queue里的顺序是两回事
【在 B*******1 的大作中提到】
: 为什么呢？
: compare 如果是true的话，a就排在b之前
: 那么less 的话，a < b就是true了
: 但是默认是max heap
: 如果push 0 - 20 进去
: queue 里面是20 19......
| d****n
发帖数: 12461 | 5 如果less是3<5，那就是最大的排在前面。如果less是5<3，重载<，那就是最小的排在
前面，明白？
【在 B*******1 的大作中提到】
: 为什么呢？
: compare 如果是true的话，a就排在b之前
: 那么less 的话，a < b就是true了
: 但是默认是max heap
: 如果push 0 - 20 进去
: queue 里面是20 19......
| S****z
发帖数: 666 | 6 我来尝试解析一下原文：
Elements are popped from the "back" of the specific container, which is
known as the top of the priority queue.
所以a是在b的前面，但是它的top是从后面开始的，
所以出现你说的“相反”的情况
where
,
【在 B*******1 的大作中提到】
: priority queue 默认就是max heap，但是它的compare函数默认是less的
: 根据compare class的描述：
: Compare: Comparison class: A class such that the expression comp(a,b), where
: comp is an object of this class and a and b are elements of the container,
: returns true if a is to be placed earlier than b in a strict weak ordering
: operation.
: 如果有a,b, a< b， 那么comp(a,b)就会return true，那么a应该放在b之前阿，但是
: 为什么会相反的呢？
| B*******1
发帖数: 2454 | 7 大牛，那么这个a在b之前究竟是什么意思呢？
【在 t****t 的大作中提到】
: compare class里说的a在b之前, 和priority queue里的顺序是两回事
| B*******1
发帖数: 2454 | 8 thanks, 我的确看漏了这行,那就是说如果container里面顺序是a,b,c,那么就pop最后
的c
但是我刚在vc2005里面try了一下，我push 了0，1，2 ,container里面的element是
c[0] = 2
c[1] = 0
c[2] = 1
现在top就是c[0]了，但是back不是c[2]吗？
谢谢各位的回答。
【在 S****z 的大作中提到】
: 我来尝试解析一下原文：
: Elements are popped from the "back" of the specific container, which is
: known as the top of the priority queue.
: 所以a是在b的前面，但是它的top是从后面开始的，
: 所以出现你说的“相反”的情况
:
: where
: ,
| t****t
发帖数: 6806 | 9 as you know priority queue is implemented with heap in . top() (i
.e. container.front()) is always the maximum element (defined by Compare()).
but when popping from the heap, the front() is swapped with back() and then
removed with container.pop_back(). so effectively pop() pops from front.
as for the order of Compare(), it is the weak ordering defined by Compare().
if you don't know what is weak ordering, never mind it.
【在 B*******1 的大作中提到】
: thanks, 我的确看漏了这行,那就是说如果container里面顺序是a,b,c,那么就pop最后
: 的c
: 但是我刚在vc2005里面try了一下，我push 了0，1，2 ,container里面的element是
: c[0] = 2
: c[1] = 0
: c[2] = 1
: 现在top就是c[0]了，但是back不是c[2]吗？
: 谢谢各位的回答。
| S****z
发帖数: 666 | 10 晕，大胆请教这样的一个简单的情况：
用数组实现最大堆的著名步骤MAX-HEAPIFY是如何把一个小元素往下挪的?
【在 B*******1 的大作中提到】
: thanks, 我的确看漏了这行,那就是说如果container里面顺序是a,b,c,那么就pop最后
: 的c
: 但是我刚在vc2005里面try了一下，我push 了0，1，2 ,container里面的element是
: c[0] = 2
: c[1] = 0
: c[2] = 1
: 现在top就是c[0]了，但是back不是c[2]吗？
: 谢谢各位的回答。
| S****z
发帖数: 666 | 11 长周末不出去转转？
(i
).
then
).
最后
【在 t****t 的大作中提到】
: as you know priority queue is implemented with heap in . top() (i
: .e. container.front()) is always the maximum element (defined by Compare()).
: but when popping from the heap, the front() is swapped with back() and then
: removed with container.pop_back(). so effectively pop() pops from front.
: as for the order of Compare(), it is the weak ordering defined by Compare().
: if you don't know what is weak ordering, never mind it.
| h*********n
发帖数: 11319 | 12 wikipedia上有代码
最后
is
【在 S****z 的大作中提到】
: 晕，大胆请教这样的一个简单的情况：
: 用数组实现最大堆的著名步骤MAX-HEAPIFY是如何把一个小元素往下挪的?
| B*******1
发帖数: 2454 | 13 thanks. now i understand.
【在 S****z 的大作中提到】
: 晕，大胆请教这样的一个简单的情况：
: 用数组实现最大堆的著名步骤MAX-HEAPIFY是如何把一个小元素往下挪的?
| B*******1
发帖数: 2454 | 14 Thanks. Now I get it.
(i
).
then
).
【在 t****t 的大作中提到】
: as you know priority queue is implemented with heap in . top() (i
: .e. container.front()) is always the maximum element (defined by Compare()).
: but when popping from the heap, the front() is swapped with back() and then
: removed with container.pop_back(). so effectively pop() pops from front.
: as for the order of Compare(), it is the weak ordering defined by Compare().
: if you don't know what is weak ordering, never mind it.
|
|
