5

嗯，我只是在学习 Scala，我正在尝试实现一些算法和数据结构。

我写了一些代码，旨在将向量转换为线性二进制堆。例如：

Vector(8,3,4,6,2,5,7,9)被转化为Vector(9,8,7,6,2,4,5,3)

这样，给定 index 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 " "
}
4

2 回答 2

4 
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))
于 2012-11-24T07:02:49.003 回答
1

向量不是平面的。它本身就是一个链表。它有一个 1:32 树，即每个节点有 32 个子节点。并按顺序填充它们。

由于您正在实现二叉堆，我们知道它是一棵平衡树。而且我们还知道，当您实现插入和删除时，树会发生一些变化。树的大小也会增加和减小。

考虑到上述事实，我建议使用可变数组对象作为主要数据类型：

var arr = Array[Int]()

通过将其声明为 var，它将更适合大小增加和减少的情况。

但是，如果您的想法只是实现一个不可变的二进制堆，也许您不需要将其声明为“var”，但我仍然建议使用 Array[Int] 而不是 Vector[Int]，因为您不需要实现堆时的链表。

更新（2012 年 12 月 1 日）：我想我会尝试使用数组来实现这种方式，几个小时后，我得到了它的工作。花了相当长的时间，并且有大量的 Scala 概念：

  1. 如何<T extends Comparable<? super T>>在 Scala 中实现 Java（有序和清单）
  2. 多个构造函数
  3. 使用Option,代替值None_Somenull
  4. 数组大小调整
  5. 实例化空数组

可能还有更多。它仍然有一些改进的余地，例如：

  1. 使用枚举而不是传递给构造函数的字符
  2. 创建一个接受函数的构造compare函数
  3. 实现 toString

但我想我会在这里完成，除非有人想添加更多内容：

package com.test
import Ordering.Implicits._

/**
 * Pass 'a' to sort ascending or 'd' to sort descending
 */
class BinaryHeap[T <% Ordered[T]: Manifest](sortingOrder: Char) {

  def this() = this('d')//Default will be descending

  var arr: Array[Option[T]] = Array.empty[Option[T]]
  var num: Int = 0

  def doCompare = {
    if (sortingOrder == 'a')
      (idx1: Int, idx2: Int) => arr(idx1).get > arr(idx2).get
    else
      (idx1: Int, idx2: Int) => arr(idx1).get < arr(idx2).get
  }

  def size: Int = num
  def add(t: T): Unit = {
    resizeIfRequired
    arr(num) = Some(t)
    swim(num)
    num = num + 1
  }

  def remove: T = {
    if (num > 0) {
      val ret = arr(0)
      num = num - 1
      swap(0, num)
      arr(num) = None: Option[T]

      sink(0)
      ret.get
    } else {
      throw new Exception("Tried to remove from an empty heap")
    }
  }

  private def resizeIfRequired: Unit = {
    if (arr.length == 0)
      arr = Array.fill(1)(None: Option[T])
    else if (num == arr.length) {
      doResize(num * 2)
    } else if (num == arr.length / 2 - 1) {
      doResize(arr.length / 2)
    }
  }

  private def doResize(newSize: Int): Unit = {
    var newArr = Array.fill(newSize)(None: Option[T])
    Array.copy(arr, 0, newArr, 0, num)
    arr = newArr
  }

  private def swim(idx: Int): Unit = {
    val parentIdx = getParent(idx)
    if (doCompare(parentIdx, idx)) {
      swap(parentIdx, idx)
      swim(parentIdx)
    }

  }

  private def swap(idx1: Int, idx2: Int) = {
    val temp = arr(idx1)
    arr(idx1) = arr(idx2)
    arr(idx2) = temp
  }

  private def sink(idx: Int): Unit = {
    val leftChildIdx = getLeftChild(idx)
    val rightChildIdx = getRightChild(idx)

    if ((isValid(leftChildIdx)) && (doCompare(leftChildIdx, idx))) {
      swap(leftChildIdx, idx)
      sink(leftChildIdx)
    } else if ((isValid(rightChildIdx)) && (doCompare(rightChildIdx, idx))) {
      swap(rightChildIdx, idx)
      sink(rightChildIdx)
    }
  }

  private def isValid(idx: Int): Boolean = {
    idx < num
  }

  private def getParent(idx: Int): Int = {
    idx / 2
  }

  private def getLeftChild(idx: Int): Int = {
    2 * idx + 1
  }

  private def getRightChild(idx: Int): Int = {
    2 * idx + 2
  }

  def printOrdered: Unit = {
    if (num == 0) {
      println("Heap is empty")
    } else {
      (0 until num) map (x => println(arr(x).get))
    }
  }

}
于 2012-11-24T04:06:00.527 回答