Binary Heap

Heap is a Purely Functional Binary Heap. Binary Heaps are not common in the functional space, especially because their implementation depends on mutable arrays in order to gain in performance. This functional binary heap is based on Vladimir Kostyukov’s paper and it does support the basic operations on a heap without compromising performance.

Supported Operations

  • add: add a value to the heap
  • remove: remove a value from the heap (it removes the min value)
  • (--) operator: remove a value from the heap (it removes the min value)
  • min: min value in the heap (it does not remove it)

  • toList: list of sorted values in the heap

Example usage:

Start by creating an empty Heap:

import cats._, cats.implicits._, cats.collections._, cats.collections.syntax.all._

val h = Heap.empty[Int]
// h: Heap[Int] = Leaf
h.isEmpty
// res0: Boolean = true

h.show
// res1: String = "Heap()"

Asking for the min value of a empty heap

h.getMin
// res2: Option[Int] = None

And we can add an item:

val h2 = h.add(12)
// h2: Heap[Int] = Branch(min = 12, left = Leaf, right = Leaf)
h2.isEmpty
// res3: Boolean = false

h2.show
// res4: String = "Heap(12)"

Let’s add a new items and ask for the min value:

val h3 = h2 + 5 + 1 + 7
// h3: Heap[Int] = Branch(
//   min = 1,
//   left = Branch(
//     min = 7,
//     left = Branch(min = 12, left = Leaf, right = Leaf),
//     right = Leaf
//   ),
//   right = Branch(min = 5, left = Leaf, right = Leaf)
// )
h3.getMin
// res5: Option[Int] = Some(value = 1)


h3.show
// res6: String = "Heap(1, 5, 7, 12)"

If we call remove it removes the min value:

val r = h3.remove
// r: Heap[Int] = Branch(
//   min = 5,
//   left = Branch(min = 7, left = Leaf, right = Leaf),
//   right = Branch(min = 12, left = Leaf, right = Leaf)
// )

r.show
// res7: String = "Heap(5, 7, 12)"

Heap sub projects

More complex implementation of Heap will be added as sub projects where each implementation can be used for specific requirements