Heap Sort in Scala

Question

Trying to implement Heap Sort in Scala

class HeapSort
{
    private def swap(array: Array[Int], lhs: Int, rhs: Int) =
    {
        val tmp = array(lhs);
        array(lhs) = array(rhs);
        array(rhs) = tmp;
    }
    private def getParent(child: Int): Int = (child - 1) / 2;
    private def getChildren(parent: Int): Tuple2[Int, Int] =
    {
        val base = parent * 2;
        return (base + 1, base + 2);
    }
    private def swapLargestValue(array: Array[Int], setRoot: (Int) => Unit, root: Int, left: Int, right: Int): Boolean =
    {
        if (array(root) >= array(left) && array(root) >= array(right)) {
            return true;
        }
        if (array(left) >= array(right)) {
            swap(array, root, left);
            setRoot(left);
        }
        else {
            swap(array, root, right);
            setRoot(right);
        }
        return false;
    }
    private def siftDown(array: Array[Int], begin: Int, end: Int): Unit =
    {
        var root = begin;
        var (left, right) = getChildren(root);
        while(left < end) {
            if (swapLargestValue(array, root = _, root, left, if (right < end) right else left)) {
                return;
            }
            val x = getChildren(root);
            left = x._1;
            right = x._2;
        }
    }
    private def heapify(array: Array[Int], end: Int): Unit =
    {
        if (end == 0) {
            return;
        }
        var start = getParent(end - 1);
        while(start >= 0) {
            siftDown(array, start, end);
            start -= 1;
        }
    }
    def heapSort(array: Array[Int]): Unit =
    {
        if (array.length <= 1) {
            return;
        }
        heapify(array, array.length);
        var end = array.length - 1;
        while(end != 0) {
            swap(array, 0, end);
            siftDown(array, 0, end);
            end -= 1;
        }
    }
}

object HS {
    def main(args: Array[String]) {
        var data = Array(5,6,7,2,3,4,8,9,1,4,6,2,8,5,4,3);
        var hs   = new HeapSort;
        hs.heapSort(data);
        println(data.deep.mkString(", "))
    }
}

Answer 1

Here is How the algorithm works with my sample code. Push all elements onto a max heap (in place). Then pop off the root node (i.e, max remaining value on heap) until you've popped all values off the heap. The values leave the heap in reverse sorted order, so as the heap shrinks, we can put popped values to the right end of the same array.

Sample code

object HeapSort {
  def main(args: Array[String]): Unit = {
    var mess = Array(3, 9, 8, 13, 2, 5, 4);

    sort(mess)
   // buildHeap(mess, mess.length-1)

    mess.foreach( println )
  }

  def sort(a: Array[Int]): Unit = {
    var m = a.length - 1 
    buildHeap(a, m)
    while (m >= 1) {
      swap(a, 0, m)
      m-=1
      heapify(a, 0, m)
    }
  }

  def buildHeap(a: Array[Int], m: Int): Unit = {
    for (i <- m/2 to 0 by -1) {
      heapify(a, i, m)
    }
  }

  /**Pushes an illegally located element down the heap to restore heap property.*/
  @annotation.tailrec
  def heapify(a: Array[Int], loc: Int, lastLeaf: Int): Unit = {
    val l = left(loc) 
    val r = right(loc)

    var max = loc

    if(l <= lastLeaf && a(l) > a(max)) max = l
    if(r <= lastLeaf && a(r) > a(max)) max = r

    if(max != loc) {
      swap(a, max, loc)
      heapify(a, max, lastLeaf)
    }
  }

  /**Returns position of left child (possibly empty). */
  def left(loc: Int): Int = {
    return 2*loc
  }

  /**Returns position of right child (possibly empty). */
  def right(loc: Int): Int = {
    return 2*loc+1
  }

  def swap(a: Array[Int], i: Int, j:Int): Unit = {
    val staging = a(i)
    a(i) = a(j)
    a(j) = staging
  }
}