c – 为什么std :: priority_queue使用max heap而不是min heap？

发布时间：2020-12-16 07:09:38 所属栏目：百科来源：网络整理

导读：我总是想知道为什么STL优先级队列默认使用max heap而不是min heap. 想到的两个明显的用例是寻路(Dijkstra)和建立霍夫曼码. 两种算法都需要先拉最小元素. 由于排序(std :: sort)默认使用升序, 我想知道priority_queue背后的设计推理是什么, 因为我非常喜欢默

我总是想知道为什么STL优先级队列默认使用max heap而不是min heap.
想到的两个明显的用例是寻路(Dijkstra)和建立霍夫曼码.
两种算法都需要先拉最小元素.
由于排序(std :: sort)默认使用升序,
我想知道priority_queue背后的设计推理是什么,
因为我非常喜欢默认的最小堆.

解决方法

Priority_queue改编自make_heap / pop_heap / push_heap / sort_heap.当make_heap with less时,元素按升序排序.最后一个元素被视为根元素.所以它是最大堆.我想有两个原因：

>我们在所有默认STL排序中总是使用较少的.> push_back()或pop_back()比push_front()或pop_front()更有效.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!