Существуют ли какие-либо реализации чисто функциональной стандартной двоичной кучи? Я знаю, что есть много интересных кучек, например: Binomial, левая куча, все они имеют функциональную реализацию, просто интересно, есть ли способ реализовать стандартную двоичную кучу, или мы должны использовать Array для ее реализации из-за неизменяемого типа? Спасибо!
Как я могу реализовать чисто функциональную стандартную двоичную кучу (ocaml или haskell)?
Ответ 1
Вам не нужен массив для реализации кучи, вы можете реализовать его как древовидную структуру.
data Heap t = Node t (Heap t) (Heap t) | Nil
Недостаток заключается в том, что вы перераспределяете O(log N) узлов для каждой операции кучи, и у вас не будет какой-либо локализации кэша для реализации на основе императивного массива. Некоторые операции будут сложны с этой структурой, но поскольку я не знаю, что вы хотите сделать с кучей, я не могу указать вам в более конкретном направлении.
Причина, по которой у нас есть специальные функциональные структуры, такие как пальцевые деревья, - ускорить определенные операции, которые вы обычно не выполняете на кучах, например, извлечение самого левого листа node. Вы можете использовать многие из тех же структур данных, которые вы изучили для императивных языков в Haskell, только с изменениями в способах обновления.
Ответ 2
Бесстыдный плагин: Браунские деревья являются идеальными кандидатами на чисто функциональную мини-кучу (или приоритетную очередь).
Ответ 3
Вы можете просмотреть идеи, описанные в этой статье Функциональный подход к стандартным двоичным кучам или в этом источнике Heap.scala.