Реализация MinMax Heap без массива

Question

Я нашел много реализаций MinMax Heap, которые хранят данные в массиве. Это очень просто реализовать, так я ищу что-то другое. Я хочу создать MinMax Heap, используя только элементы кучи с указателями на левый дочерний и правый дочерние элементы (и прикосновение к ключу для сравнения). Таким образом, куча имеет только указатель на корневой объект (минимальный уровень), а корневой объект имеет указатель на его детей (максимальный уровень) и т. Д. Я знаю, как вставить новый объект (найти правильный путь, используя двоичное представление int в зависимости от размера кучи), но я не знаю, как реализовать остальные (push up (down) элемент, найти родителя или дедушку) ,

Thx для справки

Answer 1

Это жесткий диск двоичной кучи без массива. Потому что вы должны держать все родителя во время вставки, а затем выполнять операцию нажатием вверх и вниз. как это [parent_1, parent_2 ... parant_k] and then if parent_(k+1) < parant_k pushUp и изменить их право ребенка и левого ребенка

Answer 2

heapq module source code показывает, чтобы выполнить шаги для толкания вверх и вниз. Чтобы перейти от реализации массива к реализации указателя, замените arr[2*n+1] на node.left и arr[2*n+2] на node.right. Для родительских ссылок, таких как arr[(n-1)>>1], каждому узлу нужен указатель на его родительский элемент, node.parent.

В качестве альтернативы вы можете использовать функциональный стиль, который делает все это очень простым в реализации. Я нашел код для treaps implemented in Lisp, чтобы быть источником вдохновения для того, как это сделать.

Answer 3

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