heap sort


See On Github

Data

Source Code

/*
 * A functional implementation of the heapsort algorithm
 * /
object HeapsortFunctional {
  /*
   * Witness type that allows for generic comparisons between same types.
   */
  trait >=<[A] { self =>
    def >(v1: A, v2: A): Boolean

    def <(v1: A, v2: A): Boolean

    implicit class CompOps(a: A) {
      def >(that: A): Boolean = self.>(a, that)

      def <(that: A): Boolean = self.<(a, that)
    }
  }

  @inline
  def left(i: Int): Int = (i << 1) + 1

  @inline
  def right(i: Int): Int = (i << 1) + 2

  /*
   * A heap is, essentially, a binary tree that satisfies one of two properties, max or min.
   * Functionally, this is modelled as one would model an immutable implementation of a
   * binary tree.
   */
  sealed trait Heap[+A]
  case class Node[A](a: A, left: Heap[A] = Leaf, right: Heap[A] = Leaf) extends Heap[A]
  case object Leaf extends Heap[Nothing]

  /*
   * "Sink" new nodes down the heap, whilst preserving the max heap property.
   */
  def sink[A](x: A, left: Heap[A], right: Heap[A])(implicit c: >=<[A]): Heap[A] = {
    import c._
    (left, right) match {
      case (Node(y, _, _), Node(z, l, r)) if z > y && x < z => Node(z, left, sink(x, l, r))
      case (Node(y, l, r), _) if x < y => Node(y, sink(x, l, r), right)
      case (_, _) => Node(x, left, right)
    }

  }

  /*
   * "Float" existing nodes up the heap, whilst preserving the max heap property.
   */
  def float[A](l: Heap[A], r: Heap[A])(implicit c: >=<[A]): Heap[A] = {
    import c._
    (l, r) match {
      case (Leaf, Leaf) => Leaf
      case (Leaf, n) => n
      case (n, Leaf) => n
      case (Node(a1, l1, r1), Node(a2, _, _)) if a1 > a2 => Node(a1, float(l1, r1), r)
      case (Node(a1, _, _), Node(a2, l2, r2)) if a2 > a1 => Node(a2, l, float(l2, r2))
    }
  }

  /*
   * Extract the root/head of the tree and rebalance it, such that the heap property isn't violated.
   */
  def head[A](h: Heap[A])(implicit c: >=<[A]): (Option[A], Heap[A]) = {
    h match {
      case Leaf => (None, Leaf)
      case Node(a, Leaf, l) => (Some(a), float(Leaf, l))
      case Node(a, r, Leaf) => (Some(a), float(r, Leaf))
      case Node(a, l, r) => (Some(a), float(l, r))
    }
  }

  /*
   * Given a `Vector[A]`, build a heap with a max property out of it.
   */
  def maxHeap[A](v: Vector[A])(implicit c: >=<[A]): Heap[A] = {
    def go(i: Int): Heap[A] = {
      if(i < v.length) sink(v(i), go(left(i)), go(right(i)))
      else Leaf
    }
    go(0)
  }

  /*
   * Given a `Vector[A]`, build a max heap out of it, start extracting its root and rebalance it after each extraction.
   */
  def heapsort[A](v: Vector[A])(implicit c: >=<[A]): Vector[A] = {
    @annotation.tailrec
    def go(heap: Heap[A], acc: Vector[A], s: Int): Vector[A] = {
      if(s <= 0) acc
      else head(heap) match {
        case (Some(ha), h) => go(h, acc.+:(ha), s - 1)
        case (None, h) => acc
      }
    }

    go(maxHeap(v), Vector(), v.size)
  }

}

class HeapsortFunctional_test extends WordSpec with Matchers {

  val vec = Vector(12, 42, 54, 234, 64, 340, 21, 23, 56, 40)

  implicit val witness = new >=<[Int] {
    override def >(v1: Int, v2: Int): Boolean = v1 > v2

    override def <(v1: Int, v2: Int): Boolean = v1 < v2
  }

  "A heapsort implementation" should {

    def maxheapCheck(h: Heap[Int]): Unit = h match {
      case Node(ac, Leaf, r@Node(ar, _, _)) =>
        ac >= ar shouldBe true
        maxheapCheck(r)
      case Node(ac, l@Node(al, _, _), Leaf) =>
        ac >= al shouldBe true
        maxheapCheck(l)
      case Node(ac, l@Node(al, _, _), r@Node(ar, _, _)) =>
        val leftAssertion = ac >= al
        val rightAssertion = ac >= ar
        leftAssertion shouldBe true
        rightAssertion shouldBe true

        maxheapCheck(l)
        maxheapCheck(r)
      case _ =>
    }

    @annotation.tailrec
    def balanceCheck(h: Heap[Int]): Unit = h match {
      case Leaf =>
      case _ =>
        val (_, t) = head(h)
        maxheapCheck(t)
        balanceCheck(t)
    }

    "correctly build a max heap" in {
      val heap = maxHeap(vec)
      maxheapCheck(heap)
    }

    "consistently rebalance the max heap correctly when the root is removed" in {
      val heap = maxHeap(vec)
      balanceCheck(heap)
    }

    "sort using a max heap" in {
      val withHeapsort = heapsort(vec)
      val withDefault = vec.sorted

      withHeapsort.size shouldBe withDefault.size

      (withHeapsort zip withDefault).forall(t => t._1 == t._2) shouldBe true
    }
  }
}
/*
 * An imperative implementation of the heapsort algorithm
 */
object HeapsortImperative {

  /*
   * Witness type that allows for generic comparisons between same types.
   */
  trait >=<[A] {
    self =>
    def >(v1: A, v2: A): Boolean

    def <(v1: A, v2: A): Boolean

    implicit class CompOps(a: A) {
      def >(that: A): Boolean = self.>(a, that)

      def <(that: A): Boolean = self.<(a, that)
    }

  }

  @inline
  def left(i: Int): Int = i << 1

  @inline
  def right(i: Int): Int = (i << 1) + 1

  /*
   * Fold operation over tuples.
   */
  def tupleFold[A](t: (A, A))(x: A)(f: (A, A) => A): A = t match {
    case (_1, _2) => f(f(x, _1), _2)
  }

  /*
   * Heapify, with the max heap property, given an array, a `heapsize` and an `index`.
   */
  @annotation.tailrec
  def maxheapify[A](a: Array[A], heapsize: Int, i: Int)(implicit manifest: Manifest[A], c: >=<[A]): Unit = {
    import c._

    val l = left(i)
    val r = right(i)

    val largest = tupleFold((l, r))(i) { (res, cur) =>
      if (cur < heapsize && a(cur) > a(res)) cur
      else res
    }

    if (largest != i) {
      exchange(i, largest, a)
      maxheapify(a, heapsize, largest)
    }
  }

  /*
   * Given an array, build a max heap out of it in a bottom-up manner.
   */
  def buildMaxHeap[A](a: Array[A])(implicit manifest: Manifest[A], c: >=<[A]): Array[A] = {
    for (i <- a.length >> 1 to 0 by -1) {
      maxheapify(a, a.length, i)
    }
    a
  }

  /*
   * Exchange or swap two values in an array.
   */
  def exchange[A](ia: Int, in: Int, a: Array[A]): Unit = {
    val z = a(ia)
    a(ia) = a(in)
    a(in) = z
  }

  def heapsort[A](a: Array[A])(implicit manifest: Manifest[A], c: >=<[A]): Array[A] = {
    def sort(a: Array[A]): Array[A] = {
      for (i <- (a.length - 1) until 0 by -1) {
        exchange(0, i, a)
        maxheapify(a, i, 0)
      }
      a
    }
    (buildMaxHeap[A] _ andThen sort)(a)
  }
}


class HeapsortImperative_test extends WordSpec with Matchers {

  val array = Array(12, 42, 54, 234, 64, 340, 21, 23, 56, 40)

  implicit val witness = new >=<[Int] {
    override def >(v1: Int, v2: Int): Boolean = v1 > v2

    override def <(v1: Int, v2: Int): Boolean = v1 < v2
  }

  "A heapsort implementation" should {

    @annotation.tailrec
    def maxHeapCheck(a: Array[Int], index: Int): Unit = {
      if(index < a.length) {
        val leftAssertion = if(left(index) < a.length) a(index) >= a(left(index)) else true
        val rightAssertion = if(right(index) < a.length) a(index) >= a(right(index)) else true

        leftAssertion shouldBe true
        rightAssertion shouldBe true
        maxHeapCheck(a, index + 1)
      }
    }

    "correctly build a max heap" in {
      val maxheap = buildMaxHeap(array)
      maxHeapCheck(maxheap, 0)
    }

    "sort elements using a max heap" in {
      val withHeapsort = heapsort(array).toList
      val withDefaultSort = array.sorted.toList

      withHeapsort.size shouldBe withDefaultSort.size

      (withHeapsort zip withDefaultSort).forall(t => t._1 == t._2) shouldBe true
    }
  }

}