Need advice implementing a binary heap structure in Scala

algorithm, data-structures, scala

Solution

import scala.math.Ordering.Implicits._

def insert[T : Ordering](heap: Vector[T], newItem: T) = {
  @annotation.tailrec
  def siftUp(h: Vector[T], idx: Int):Vector[T] = {
    val parentIdx = (idx - 1) >> 1
    if(parentIdx < 0 || h(parentIdx) > h(idx)) h
    else siftUp(h.updated(parentIdx, h(idx)).updated(idx, h(parentIdx)), parentIdx)
  }

  siftUp(heap :+ newItem, heap.length)
}
def heapify[T: Ordering](vs: Vector[T]) = vs.foldLeft(Vector.empty[T])(insert)

assert(heapify(Vector(8, 3, 4, 6, 2, 5, 7, 9)) == Vector(9, 8, 7, 6, 2, 4, 5, 3))

Problem

Well I'm just learning Scala and I'm trying to implement some algorithms and data structures. I wrote some code that aims to transform a Vector in a linear binary heap. For instance: `Vector(8,3,4,6,2,5,7,9)` is transformed to `Vector(9,8,7,6,2,4,5,3)` In this way, given index `i`, its parent is at: `(i-1)/2` or `(i-2)/2` depending on `i` being odd or pair. I leave the code here, What I'm looking for is some advice on how could I improve my implementation. Or even try it out in another completely different direction. You can use this like: `new Heap(Vector(8,3,4,6,2,5,7,9))` ``` class Heap(vs: Vector[Int]) { val heap = build() private def build():Vector[Int] = { ((1 until vs.length) foldLeft Vector[Int](vs.head)) ( (accu, idx) => fixFrom(accu :+ vs(idx), idx) ) } private def fixFrom(heapToFix:Vector[Int], idx: Int): Vector[Int] = { val parentIndex = parent(idx) if(parentIndex == -1 || heapToFix(idx) <= heapToFix(parentIndex)) heapToFix else { val nextToFix = (heapToFix.updated(parentIndex, heapToFix(idx))) take idx val fixed = fixFrom(nextToFix, parentIndex) val swap = heapToFix.updated(idx, heapToFix(parentIndex)) fixed ++ (swap drop idx) } } def children(parentIndex: Int) = (valid(2*parentIndex + 1), valid(2*parentIndex + 2)) def parent(childIndex: Int) = if(childIndex % 2 == 0) valid((childIndex-2)/2) else valid((childIndex-1)/2) def valid(idx:Int) = if(idx >= 0 && idx < vs.length) idx else -1 override def toString = heap mkString " " } ``` Update 1: Taking the advices below, I've done some changes: ``` import math.Ordering.Implicits._ class Heap[T: Ordering](vs: Vector[T]) { val heap = build() private def build():Vector[T] = ((0 until vs.length) foldLeft Vector.empty[T]) ( (accu, idx) => fixUp(accu :+ vs(idx), idx) ) @annotation.tailrec private def fixUp(h:Vector[T], idx: Int): Vector[T] = { val parentIdx = parent(idx) if(parentIdx < 0 || h(idx) <= h(parentIdx)) h else fixUp(h.updated(parentIdx, h(idx)).updated(idx, h(parentIdx)), parentIdx) } def parent(idx: Int) = (idx-1) >> 1 override def toString = heap mkString " " } ```

Original source