Почему приоритетную очередь предпочтительнее реализовать с помощью кучи, а не по массиву, хотя сама куча реализована с использованием массива

Question

Почему очередь приоритетов предпочтительнее реализовывать с использованием кучи, а не массива, хотя сама куча реализована с использованием массива.

Answer 1

Бинарная куча обеспечивает частичное упорядочение, которое гарантирует вставку O (log n) и удаление O (log n) элемента с наивысшим приоритетом.

Для плоского массива у вас есть два варианта:

1. Поддерживать упорядоченный массив.Вставка становится операцией O (n), а удаление элемента с наивысшим приоритетом - O (1).
2. Вставьте элементы в порядке их получения.В этом случае вставка становится O (1), а удаление элемента с наивысшим приоритетом - O (n).

Любой из этих двух параметров делает очередь приоритета менее эффективной, чем при реализации двоичной кучи.