Структуры данных: если кучи — это деревья, почему они реализованы внутри со списками или массивами?

Вкратце: сэкономьте на памяти, получите больше скорости за счет локализации данных.

Для двоичного дерева вам нужно в каждом узле 4 байта для левого дочернего элемента и 4 байта для правого дочернего элемента (или 8 + 8, если вы работаете в 64-битной системе). Это просто голые указатели, которые вам нужны. Если вы храните 32-битный int, это много накладных расходов. Добавьте еще один указатель на родителя, который необходим для перемещения узла к корню, и вы увидите 24 байта служебных данных для 4-байтового целого числа в 64-битной системе.

Для кучи вам не нужно беспокоиться о произвольных деревьях. Обычно вы беспокоитесь только о головке (минимум/максимум значений) и не заботитесь о внутренней структуре. Куча представляет собой почти полное бинарное дерево (заполнены все уровни, кроме последнего, который заполняется слева направо). В этой структуре, если вы просто поместите узлы в массив, то для узла с индексом x вы всегда найдете родителя в (x+1)/2, левого дочернего элемента в x*2+1 и правого дочернего элемента в x*2+2. Так что нет необходимости хранить какие-либо из этих толстых указателей.

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

Конечно, если это не то, где важна эффективность, вы можете реализовать его как обычное дерево. И наоборот, если у вас есть почти полное дерево и вы хотите максимально эффективно использовать систему, реализуйте его с помощью массива (даже если вы не используете его как кучу).

Для начала сделаем небольшое уточнение по лексике:

• Очередь приоритетов (минимально-ориентированная, но я не буду уточнять каждый раз) — это абстрактная структура данных, которая реализует операции add и deleteMin, а иногда и decreaseKey. На самом деле, вы можете создать простой массив/список, в котором вы перебираете структуру, чтобы найти минимум, и вы бы реализовали приоритетную очередь (очень неэффективную, но все же).
• A heap is a tree-based data structure that satisfies the heap property (Википедия). Свойство кучи: родитель имеет меньший ключ, чем его дочерние элементы.
• Структура данных, которую вы описываете, представляет собой очень распространенную бинарную кучу, которая является своего рода кучей, но не единственный. (Не самый эффективный, но это уже другая история).

Когда я впервые услышал о двоичной куче, я также подумал, что очень странно иметь дерево в массиве, и вам придется делать какие-то странные умножения, чтобы добраться до потомков/родителей.

Это сложнее представить в голове, но это имеет смысл, если вы посмотрите немного поближе:

• Двоичная куча почти сбалансирована, то есть в массиве никогда не будет дыры. (Это простое свойство прекрасно само по себе, потому что дыры в массивах — настоящая боль).
• Он занимает меньше места: массив НАМНОГО эффективнее использует память, чем узлы.
• Поскольку он разработан, довольно легко абстрагировать массив как двоичное дерево. Вы можете создать помощники, такие как getRight(int node), getLeft(int node) и getParent(int node), и реализация будет выглядеть более знакомой.

Однако двоичная куча неэффективна с точки зрения кэширования, поскольку дочерние элементы находятся очень далеко от родителя, хотя она может быть более эффективной с точки зрения кэширования, чем эквивалентная двоичная куча на основе узлов.

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

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

Однако другие виды куч реализуются с помощью узлов, так что это особый случай.