5

さて、私はScalaを学んでいて、いくつかのアルゴリズムとデータ構造を実装しようとしています。

ベクトルを線形バイナリヒープに変換することを目的としたコードをいくつか作成しました。例えば：

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 " "
}
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」と宣言する必要はありませんが、Vector[Int]ではなくArray[Int]を使用することをお勧めします。ヒープを実装するときのリンクリスト。

更新（2012年12月1日）：配列を使用してこの方法を実装しようとすると、いくつかの練習ができると考え、数時間後には機能するようになりました。かなりの時間がかかり、Scalaのコンセプトがたくさんあります。

  1. ScalaでJavaを実装する方法<T extends Comparable<? super T>>（順序付きおよびマニフェスト）
  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 に答える