Как я могу реализовать чисто функциональную стандартную двоичную кучу (ocaml или haskell)?

Question

Есть ли реализации чисто функциональной стандартной двоичной кучи?Я знаю, что есть много интересных куч, например: биномиальная, левая куча, все они имеют функциональную реализацию, просто интересно, есть ли способ реализовать стандартную двоичную кучу или мы должны использовать Array для ее реализации из-за неизменяемого типа?Спасибо!

Answer 1

Вам не нужен массив для реализации кучи, вы можете реализовать его как древовидную структуру.

data Heap t = Node t (Heap t) (Heap t) | Nil

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

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

Answer 2

Бесстыдный плагин: Деревья Брауна - идеальные кандидаты для чисто функциональной мини-кучи (или очереди с приоритетами).

Answer 3

Вы можете просмотреть идеи, описанные в этой статье. Функциональный подход к стандартным двоичным кучам или в этом источнике Heap.scala .