嗯,我只是在学习 Scala,我正在尝试实现一些算法和数据结构。
我写了一些代码,旨在将 Vector 转换为线性二叉堆。例如:
Vector(8,3,4,6,2,5,7,9)
转换为 Vector(9,8,7,6,2,4,5, 3)
这样,给定索引i
,它的parent在:(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 " "
}
最佳答案
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))
关于algorithm - 需要在 Scala 中实现二进制堆结构的建议,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13537805/