Почему std::priority_queue использует max heap вместо min heap?

Question

Мне всегда было интересно, почему в очереди приоритетов STL по умолчанию используется максимальная куча, а не минимальная куча. На ум приходят два очевидных варианта использования: поиск пути (Dijkstra) и построение кодов Хаффмана. Оба алгоритма должны сначала извлекать минимальные элементы. Так как сортировка (std::sort) по умолчанию использует возрастающий порядок, мне интересно, каковы были причины проекта priority_queue, потому что я бы очень предпочел минимальную кучу по умолчанию.

Answer 1

Priority_queue адаптируется из make_heap/pop_heap/push_heap/sort_heap. Когда вы делаете с меньшим количеством элементов, элементы сортируются по возрастанию. И последний элемент рассматривается как корневой элемент. Так что это максимальная куча. Я думаю, есть две причины:

1. Мы всегда используем меньше во всех стандартных сортировках STL.
2. push_back () или pop_back() гораздо более эффективны, чем push_front() или pop_front().

Answer 2

Есть причина, но это связано с взаимосвязанными функциями C++.

priority_queue был разработан, чтобы быть простым в использовании оберткой вокруг make_heap, pop_heap а также push_heap, Для функций кучи имеет смысл сохранять наибольшее значение в начале, потому что это то, что вам нужно для реализации sort_heap, которые также используют функции кучи.

Конечно, вы всегда можете создать экземпляр priority_queue с greater скорее, чем less чтобы получить поведение, которое вы хотите.

Answer 3

В английском языке сначала должно произойти что-то более важное. Следовательно, в очереди с приоритетом сначала должно выталкиваться что-то с более высоким приоритетом.

В основном ответ на ваш вопрос заключается в том, что определение приоритета слова настоятельно подразумевает упорядочение от наибольшего к наименьшему.

Только представьте себе очередь с приоритетом вроде вестибюля больницы. Пациенты с наибольшим приоритетом (неотложные случаи) должны стоять в очереди на лечение.