为什么 std::priority_queue 使用最大堆而不是最小堆?

问题描述

我一直想知道为什么 STL 优先级队列默认使用最大堆而不是最小堆.我想到的两个明显用例是寻路 (Dijkstra) 和构建霍夫曼代码.两种算法都需要先拉取最小元素.由于排序 (std::sort) 默认使用升序，我想知道priority_queue背后的设计推理是什么，因为我更喜欢默认情况下最小堆.

I always wondered why STL priority queue uses max heap instead of min heap by default.Two obvious use cases that come to mind is pathfinding (Dijkstra) and building Huffman codes.Both algorithms need to pull min elements first.Since sorting (std::sort) uses ascending order by default,I wonder what was the design reasoning behind priority_queue,because I would very much prefer a min heap by default.

推荐答案

Priority_queue 改编自 make_heap/pop_heap/push_heap/sort_heap.当您使用 less 进行 make_heap 时，元素按升序排列.最后一个元素被视为根元素.所以它是最大堆.我想有两个原因:

Priority_queue is adapted from make_heap/pop_heap/push_heap/sort_heap. When you make_heap with less, the elements are sorted ascending. And the last element is treated as root element. So it is max heap. I guess there are two reasons:

1. 我们总是在所有默认 STL 排序中使用 less.
2. push_back() 或 pop_back() 比 push_front() 或 pop_front() 效率高得多.

这篇关于为什么 std::priority_queue 使用最大堆而不是最小堆?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！