Я всегда считал , что отвалы и приоритетные очереди были синонимами - абстрактная структура данных , которая поддерживает insert, findMinи deleteMinоперации.
Некоторая литература, кажется, согласна со мной - например, чисто функциональные структуры данных Криса Окасаки (глава 3).
С другой стороны, страница кучи Википедии определяет ее как древовидную структуру данных и утверждает, что кучи являются конкретной реализацией очередей с приоритетами.
Мне трудно с этим смириться с тем фактом, что я могу думать о более чем одной реализации кучи - левые кучи, биномиальные кучи, сплайс-кучи ...
Разве простой факт, что куча может быть реализована с различными структурами данных, не означает, по определению, что это абстрактная структура данных? И если это так, то есть ли реальная разница с приоритетными очередями?
источник
Ответы:
Очередь с приоритетом может иметь любую реализацию, например, массив, который вы ищите линейно, когда всплываете. Все это означает, что, когда вы щелкаете, вы получаете значение с минимальным или максимальным в зависимости.
Классическая куча, как ее обычно называют, обычно представляет собой кучу мин. Реализация, которая имеет хорошую сложность времени (
O(log n)на push и pop) и не требует дополнительной памяти.источник
findMin,deleteMin,insert), отвалы имеют гарантированные «хорошие» Сложности для них , где очередей приоритетов нет?O(log(n)), я думаю , не будет толчка и попса.Этот сайт дает действительно четкое объяснение. http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html
Короче говоря, приоритетная очередь может быть реализована с использованием многих структур данных, которые мы уже изучили (массив, связанный список или двоичное дерево поиска). Однако эти структуры данных не обеспечивают наиболее эффективные операции. Чтобы сделать все операции очень эффективными, мы будем использовать новую структуру данных, которая называется кучей.
источник
Я думаю, что то, что вы написали о конкретных против абстрактных, является правильным. Там, где вы говорите, что кучи наложения, биномиальные кучи - это разные реализации кучи, хотя, я думаю, правильнее будет сказать, что это разные типы кучи. Куча - это категория реализации, которая обычно гарантирует не только один и тот же интерфейс, но и одинаковое время доступа.
Вы видите это с ассоциативными картами, а также с хеш-таблицами и бинарными деревьями поиска. Bsts и хеш-таблицы - это конкретные структуры данных, которые предоставляют абстрактный интерфейс ассоциативной карты. Красные чёрные деревья и деревья avl являются сбалансированными bsts, с одинаковыми большими O-гарантиями и одинаковым дополнительным интерфейсом (в порядке обхода). Это разные типы деревьев, я бы сказал больше, чем разные реализации деревьев. Это разные, но тесно связанные реализации ассоциативных карт.
источник