title: Need advice implementing a binary heap structure in Scala
body: <p>Well I'm just learning Scala and I'm trying to implement some algorithms and data structures.</p>
  
  <p>I wrote some code that aims to transform a Vector in a linear binary heap. For instance:</p>
  
  <p><code>Vector(8,3,4,6,2,5,7,9)</code> is transformed to <code>Vector(9,8,7,6,2,4,5,3)</code></p>
  
  <p>In this way, given index <code>i</code>, its parent is at: <code>(i-1)/2</code> or <code>(i-2)/2</code> depending on <code>i</code> being odd or pair.</p>
  
  <p>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. </p>
  
  <p>You can use this like: <code>new Heap(Vector(8,3,4,6,2,5,7,9))</code></p>
  
  <pre><code>class Heap(vs: Vector[Int]) {
    val heap = build()
  
    private def build():Vector[Int] = {   
      ((1 until vs.length) foldLeft Vector[Int](vs.head)) ( (accu, idx) =&gt;
          fixFrom(accu :+ vs(idx), idx) )
    }
  
    private def fixFrom(heapToFix:Vector[Int], idx: Int): Vector[Int] = {
        val parentIndex = parent(idx)
        if(parentIndex == -1 || heapToFix(idx) &lt;= 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 &gt;= 0 &amp;&amp; idx &lt; vs.length) idx else -1
  
    override def toString = heap mkString " "
  }
  </code></pre>
  
  <p>Update 1: Taking the advices below, I've done some changes:</p>
  
  <pre><code>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) =&gt;
          fixUp(accu :+ vs(idx), idx) )
  
    @annotation.tailrec       
    private def fixUp(h:Vector[T], idx: Int): Vector[T] = {
        val parentIdx = parent(idx)
        if(parentIdx &lt; 0 || h(idx) &lt;= h(parentIdx)) h
        else fixUp(h.updated(parentIdx, h(idx)).updated(idx, h(parentIdx)), parentIdx)
    }
  
    def parent(idx: Int) = (idx-1) &gt;&gt; 1
  
    override def toString = heap mkString " "
  }
  </code></pre>