algorithm – 需要在Scala中实现二进制堆结构的建议

我写了一些代码,旨在转换线性二进制堆中的Vector.例如：

矢量(8,3,4,6,2,5,7,9)转换为Vector(9,8,3)

以这种方式,给定索引i,其父亲处于：(i-1)/ 2或(i-2)/ 2,这取决于i是奇数还是对.

我把代码保留在这里,我正在寻找的是关于如何改进我的实现的一些建议.或者甚至在另一个完全不同的方向尝试.

你可以使用这个：new Heap(Vector(8,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 " "
}

更新1：根据以下建议,我做了一些更改：

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