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

Question

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

Спасибо за помощь

Answer 1

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

Answer 2

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

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

Answer 3

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

У меня есть несколько реализаций в Java и C ++, реализующих MinHeap с массивами и без них. Смотрите мои реализации Java для решения. И да, очень возможно реализовать Heap без массивов. Вам просто нужно запомнить, куда вставить следующий узел и как выполнить heapify и выполнить обратное heapify.

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

Answer 4

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