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

Question

好吧,我只是学习Scala,我正在尝试实现一些算法和数据结构.

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

Vector(8,3,4,6,2,5,7,9) 变成了 Vector(9,8,7,6,2,4,5,3)

通过这种方式,给定索引i,其父级位于:(i-1)/2或(i-2)/2取决于i奇数或对.

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

你可以这样使用: 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 " "
}

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

Answer 1

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