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(", "))
 }
}

• Loki Astari: @Heslacher: No. It was supposed to be siftDown(). It seems to be the standard name for that operation: stackoverflow.com/questions/34329942/…

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

• Mast: You've presented an alternative solution without reviewing the code. On Code Review, all answers should contain a review.
• Loki Astari: Consider this: loc=0;left=1;right=2;Now think about your definition of left() and right(). Your code is correct if you assume arrays are indexed from 1.
• Loki Astari: Thanks for the code couple of questions. Why do you use recursion instead of a loop in heapify(). In my code when getting the children I use a tuple and one call. You use two calls (left() and right()). Is there a particular reason you choose to use two functions. Is my code bad practice or OK?
• Loki Astari: All your methods are public. I tried to hide members that were not useful to the public scope. Is that bad?