# 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

• 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)"
``````

``````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