## heap sort

### Data

in scala

#### Tags

selection sort, sorting

### 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
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 _ =>
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
}
}

}
``````