Binary Heap (Priority Queue)

Algorithm

Operation	Complexity
Construct	$O(n)$
Enqueue	$O(logn)$
Dequeue	$O(logn)$

Implementation

import cats.{Order, Show}
import cats.implicits._

sealed abstract class BinaryHeap[A](val toVector: Vector[A])(
    implicit O: Order[A]) {

  import BinaryHeap._

  def enqueue(a: A): BinaryHeap[A] =
    new BinaryHeap(swim(toVector :+ a, toVector.length)) {}

  def dequeue: (Option[A], BinaryHeap[A]) =
    toVector.lift(1) -> new BinaryHeap(
      sink(toVector.updated(1, toVector(toVector.length - 1)).dropRight(1), 1)
    ) {}
}

object BinaryHeap {

  private def swim[A](repr: Vector[A], i: Int)(
      implicit O: Order[A]): Vector[A] = {
    val parentI = i / 2
    if (parentI > 0) {
      if (O.compare(repr(parentI), repr(i)) > 0)
        swim(
          repr.updated(parentI, repr(i)).updated(i, repr(parentI)),
          parentI
        )
      else repr
    } else repr
  }

  private def sink[A](repr: Vector[A], i: Int)(
      implicit O: Order[A]): Vector[A] = {

    val ORD = Order.by[(Int, A), A](_._2)

    val leftChildI = i * 2
    val rightChildI = leftChildI + 1
    if (i < repr.length) {
      val pos = i -> repr(i)
      if (leftChildI < repr.length) {

        val res = { pos: (Int, A) =>
          if (rightChildI < repr.length)
            ORD.min(pos, rightChildI -> repr(rightChildI))
          else pos
        }.apply(
          ORD.min(pos, leftChildI -> repr(leftChildI))
        )

        if (res == pos) repr
        else {
          val (swapI, swapElem) = res
          sink(repr.updated(i, swapElem).updated(swapI, repr(i)), swapI)
        }
      } else repr
    } else repr
  }

  def apply[A](as: A*)(dummy: A)(
      implicit O: Order[A]
  ): BinaryHeap[A] = {
    new BinaryHeap[A](
      (as.length / 2).to(1, -1).toList.foldLeft((dummy +: as).toVector)(sink)
    ) {}
  }

  def apply[A](dummy: A)(
      implicit O: Order[A]
  ): BinaryHeap[A] =
    new BinaryHeap[A](Vector(dummy)) {}

  implicit def show[A: Show]: Show[BinaryHeap[A]] =
    Show.show(bh => Show[Vector[A]].show(bh.toVector))
}