4
\$\begingroup\$

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(", "))
    }
}
\$\endgroup\$
1

1 Answer 1

1
\$\begingroup\$

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
  }
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ You've presented an alternative solution without reviewing the code. On Code Review, all answers should contain a review. \$\endgroup\$
    – Mast
    Feb 1, 2017 at 9:46
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 1, 2017 at 16:39
  • \$\begingroup\$ 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? \$\endgroup\$ Feb 1, 2017 at 16:46
  • \$\begingroup\$ All your methods are public. I tried to hide members that were not useful to the public scope. Is that bad? \$\endgroup\$ Feb 1, 2017 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.