Блог

В справочном руководстве OCaml приведен пример реализации очереди приоритетов.

Это графическая реализация кучи. Я сказал «куча», потому что каждый узел имеет 0, 1 или 2 дочерних узла, а родительский узел меньше или равен его дочерним узлам. Однако это не «двоичная куча», поскольку алгоритм вставки не заставляет листья выравниваться по крайнему левому краю (как это должно быть в соответствии с определением Википедии), поэтому дерево не является полным.

Моя интуиция подсказывает, что дерево сбалансировано, так как каждый раз, когда мы вставляем новый узел: левое поддерево перемещается в правое поддерево, а предыдущее правое поддерево добавляет узел и становится новым левым поддеревом. Следующая вставка переместит ранее вызванное «новое правое поддерево» влево и добавит узел.

Таким образом, глубина левого поддерева никогда не отличается более чем на 1 от глубины правого поддерева, поэтому дерево сбалансировано. Следовательно, мы никогда не должны оказаться в дереве, имеющем форму связанного списка, и сложность в наихудшем случае должна оставаться O (log n) — в то время как алгоритм вставки намного проще, поскольку он не заботится о сохранении дерева полным (но только сбалансированным).

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

Спасибо

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

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

Таким образом, эта куча не дает никакой гарантии O (log N), если N — размер кучи. Однако это происходит, если N — общее количество вставок, и это не так уж плохо. Это не влияет на сложность большинства алгоритмов, использующих кучи.