Куча и приоритетная очередь, структуры данных или абстрактные типы данных?

Question

Я видел похожие вопросы и прочитал много ответов. Можно было бы подумать, что я узнаю об этом тогда, однако некоторые ответы были противоречивыми, и теперь я более запутан, чем когда я начал.

Мой квест начался как - в чем разница между кучей и приоритетом Очередь. Там, где я узнал, что Heap - это структура данных, а Priority Queue - абстрактный тип данных. Но почему?

Пока я нашел этот ответ лучшим: Проще говоря, отношение между структурой данных и абстрактным типом данных такое же, как отношение между алгоритмом и псевдокодом. Первая - это идея, вторая - формальное описание (абстрактное, недоступное).

Некоторые упоминают, что ADT является языковым термином. Поскольку он описывает «типы данных, не включенные в стандартную библиотеку». Таким образом, в Java или JS кучи нет в стандартной библиотеке, но ранее я узнал, что кучи являются структурой данных, а не абстрактным типом данных?

Может ли кто-нибудь вообще уточнить, что такое структура данных а абстрактный тип данных есть?

Answer 1

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

A Куча - это структура данных, способ ее хранения данные и то, как они работают с ними, хорошо определены.

Использование кучи для реализации очереди с приоритетами - хорошая идея, поскольку способ работы кучи с данными очень хорошо согласуется с тем, как работает очередь с приоритетами. Если вы посмотрите документацию на java.util.PriorityQueue, то увидите следующий комментарий:

Неограниченная очередь с приоритетами на основе приоритета heap

Вы можете представить ADT как логическое описание высокого уровня (что он делает), в то время как структура данных точно определяет, как данные хранятся и обрабатываются (как это делается).

Не могли бы вы реализовать очередь приоритетов, использующая какую-то другую структуру данных? конечно, вероятно, не так эффективно, хотя.