priority_queue C++ implementation# JobHunting - 待字闺中
a*r
1 楼
下面的代码work，但是至少有一个nasty bug，大家猜猜看？
还有，请对代码提意见：
还有，请对代码提意见：
a*m
2 楼
sublime? //hand
a*r
3 楼
ya, love it
【在 a********m 的大作中提到】
: sublime? //hand
a*m
4 楼
嗯。俺重装系统以后就压根没装vs了，而且几个os都有，没有换编辑器的问题。
【在 a***r 的大作中提到】
:
: ya, love it
【在 a***r 的大作中提到】
:
: ya, love it
a*r
5 楼
大牛能指教一下我的C++code吗?
我有一段时间没写C++code了，任何建议，我洗耳恭听.
我有一段时间没写C++code了，任何建议，我洗耳恭听.
a*m
6 楼
随便扫了一眼，没啥特别明显问题。move_down看起来有点怪，你可以再检查一下。
s*s
7 楼
推荐几个sublime最常用的插件吧？python, c++用的。
a*r
8 楼
我都是从这个list上找，看那个最popular：
http://wbond.net/sublime_packages/community#sort-installs
【在 s*********s 的大作中提到】
: 推荐几个sublime最常用的插件吧？python, c++用的。
a*r
9 楼
move_down处理的item比较多：
》有没有child:
没有，只有左，有左右（和左还是右对换）
》minQueue和maxQueue比较的不同
我加了些comment.还是有点乱。
大牛如果你写，会怎么写？
【在 a********m 的大作中提到】
: 随便扫了一眼，没啥特别明显问题。move_down看起来有点怪，你可以再检查一下。
a*m
10 楼
写成递归可能代码简单点。
【在 a***r 的大作中提到】
:
: move_down处理的item比较多：
: 》有没有child:
: 没有，只有左，有左右（和左还是右对换）
: 》minQueue和maxQueue比较的不同
: 我加了些comment.还是有点乱。
: 大牛如果你写，会怎么写？
【在 a***r 的大作中提到】
:
: move_down处理的item比较多：
: 》有没有child:
: 没有，只有左，有左右（和左还是右对换）
: 》minQueue和maxQueue比较的不同
: 我加了些comment.还是有点乱。
: 大牛如果你写，会怎么写？
p*p
11 楼
恕我眼拙，LZ说的BUG在哪，请明示
l*8
12 楼
我写了个moveDown
a*r
13 楼
不错，不过:
if(rightIdx>size())
shouldn't it be:
if(rightIdx<=size()-1)
?
【在 l*********8 的大作中提到】
: 我写了个moveDown
l*8
14 楼
yes, you're right!
正如秋虫大牛所说，递归的话更简单：
【在 a***r 的大作中提到】
:
: 不错，不过:
: if(rightIdx>size())
: shouldn't it be:
: if(rightIdx<=size()-1)
: ?
正如秋虫大牛所说，递归的话更简单：
【在 a***r 的大作中提到】
:
: 不错，不过:
: if(rightIdx>size())
: shouldn't it be:
: if(rightIdx<=size()-1)
: ?
l*8
15 楼
同问，我也没看出这个bug
【在 p*****p 的大作中提到】
: 恕我眼拙，LZ说的BUG在哪，请明示
【在 p*****p 的大作中提到】
: 恕我眼拙，LZ说的BUG在哪，请明示
a*r
16 楼
bug 在 size_t 上。
when comparing:
while(i
size()-1 is (2^32-1)
very nasty.
【在 p*****p 的大作中提到】
: 恕我眼拙，LZ说的BUG在哪，请明示
l*8
17 楼
哦，是啊。 的确是不容易注意的一个bug
【在 a***r 的大作中提到】
:
: bug 在 size_t 上。
: when comparing:
: while(i
: size()-1 is (2^32-1)
: very nasty.
【在 a***r 的大作中提到】
:
: bug 在 size_t 上。
: when comparing:
: while(i
: size()-1 is (2^32-1)
: very nasty.
l*8
18 楼
if (child > size())
应该是
if (child >= size())
【在 l*********8 的大作中提到】
: yes, you're right!
: 正如秋虫大牛所说，递归的话更简单：
应该是
if (child >= size())
【在 l*********8 的大作中提到】
: yes, you're right!
: 正如秋虫大牛所说，递归的话更简单：
q*z
19 楼
我看C++的文档说push是O(1)时间，这个实现的好像不是O（1）？
a*r
20 楼
My implementation is based on BinaryHeap,insert's worst-case cost is O(logN)
Fibonacci Heap's insert amortized cost is O(1)
which C++ document are you referring to?
【在 q*******z 的大作中提到】
: 我看C++的文档说push是O(1)时间，这个实现的好像不是O（1）？
q*z
21 楼
http://www.cplusplus.com/reference/queue/priority_queue/push/
logN)
【在 a***r 的大作中提到】
:
: My implementation is based on BinaryHeap,insert's worst-case cost is O(logN)
: Fibonacci Heap's insert amortized cost is O(1)
: which C++ document are you referring to?
logN)
【在 a***r 的大作中提到】
:
: My implementation is based on BinaryHeap,insert's worst-case cost is O(logN)
: Fibonacci Heap's insert amortized cost is O(1)
: which C++ document are you referring to?
a*r
22 楼
Complexity
Constant (in the priority_queue). Although notice that push_heap operates
in logarithmic time.
I think it means the time spent inside priority_queue is O(1),if adding in
push_heap, the overall complexity should be O(lgN).
【在 q*******z 的大作中提到】
: http://www.cplusplus.com/reference/queue/priority_queue/push/
:
: logN)
q*z
23 楼
yes, it depends on the heap type
【在 a***r 的大作中提到】
:
: Complexity
: Constant (in the priority_queue). Although notice that push_heap operates
: in logarithmic time.
: I think it means the time spent inside priority_queue is O(1),if adding in
: push_heap, the overall complexity should be O(lgN).
【在 a***r 的大作中提到】
:
: Complexity
: Constant (in the priority_queue). Although notice that push_heap operates
: in logarithmic time.
: I think it means the time spent inside priority_queue is O(1),if adding in
: push_heap, the overall complexity should be O(lgN).
b*7
24 楼
与std::priority_queue语义不太一致。std::priority_queue,std::less
>得到的是max heap，而你的priority_queue >得到的是min heap
【在 a***r 的大作中提到】
: 下面的代码work，但是至少有一个nasty bug，大家猜猜看？
: 还有，请对代码提意见：
【在 a***r 的大作中提到】
: 下面的代码work，但是至少有一个nasty bug，大家猜猜看？
: 还有，请对代码提意见：
r*n
25 楼
priority queue其实最好index从1开始，这样parent一个表达式就出来了：k/2，left
child是2k，right child2k+1
看下面链接的实现，比较简洁
http://algs4.cs.princeton.edu/24pq/
child是2k，right child2k+1
看下面链接的实现，比较简洁
http://algs4.cs.princeton.edu/24pq/
d*x
26 楼
less的作用是提供一个偏序
在这个偏序下"最大"的元素将被放在堆顶。。。这有啥不能理解的啊！！！
where
,
operator
same
在这个偏序下"最大"的元素将被放在堆顶。。。这有啥不能理解的啊！！！
where
,
operator
same
b*n
27 楼
不好意思,问的太笼统了
我不能理解的是如果用less 而且" returns true if a is to be placed earlier
than b", 那么不应该是越小排在越前面,这样不就是min heap了? 为什么是max heap?
求指教
我不能理解的是如果用less
than b", 那么不应该是越小排在越前面,这样不就是min heap了? 为什么是max heap?
求指教
d*x
28 楼
人家就不能用less找出最大的嘛！
earlier
【在 b*******n 的大作中提到】
: 不好意思,问的太笼统了
: 我不能理解的是如果用less 而且" returns true if a is to be placed earlier
: than b", 那么不应该是越小排在越前面,这样不就是min heap了? 为什么是max heap?
: 求指教
earlier
【在 b*******n 的大作中提到】
: 不好意思,问的太笼统了
: 我不能理解的是如果用less
: than b", 那么不应该是越小排在越前面,这样不就是min heap了? 为什么是max heap?
: 求指教
相关阅读
想起一个问题，fastest algorithm for sorting small datah1b transfer 加急一问 (转载)有人知道SAS是不是不sponsor H1bPart-time furniture store sales wanted啥是W2, 1099, corp-to-corp contract?关于trie和binary search tree的疑问。客户端性能分析调整--请教！求教一道经典面题的解法Interview Questions for an investment bank昨晚的Google Intern Interview一个老板加一个下属算一个team吗？OPT电话加急大公司的HR都TMD的王八蛋为什么不见有人到fujitsu工作?无聊，在网上查工资现在CS和统计，那个好找工作？纪念毕业一年又被HR放鸽子关于out of status and opt 的一些问题 (转载)昨天有人贴了个长list的编程题