按非大小写字段排序 PriorityQueue class

Question

我目前正在尝试使用 scala 实现霍夫曼算法。为此，我想我会使用 PriorityQueue 根据权重对树中的不同节点进行排序。因此，我必须创建一个 BinarySearchTree 节点的 PriorityQueue。但是，Scala 只允许我按案例 class.

的字段排序

这是我想要的：

  class BinarySearchTree(weight: Int)
  case class ForkNode(left: BinarySearchTree, right: BinarySearchTree, chars: List[Char], weight: Int) extends BinarySearchTree(weight)
  case class LeafNode(char: Char, weight: Int) extends BinarySearchTree(weight)

  def createBST(inputFile: ListMap[Char,Int]): BinarySearchTree = {
    def weightOrder(t2: BinarySearchTree) = t2.weight
    val nodeMap:PriorityQueue[BinarySearchTree] = PriorityQueue(Ordering.by(weightOrder))
    null
  }

但它无法编译。但是，def weightOrder(t2: ForkNode) = t2.weight 确实可以编译，但这不是我想要的。

如何根据非大小写的字段对我的优先级队列进行排序 class？

Answer 1

这是不完整的，但可以编译。

import scala.collection.immutable.ListMap
import collection.mutable.PriorityQueue

class BinarySearchTree(val weight: Int)  //weight is now member data

case class ForkNode( left: BinarySearchTree
                   , right: BinarySearchTree
                   , chars: List[Char]
                   , override val weight: Int  //now needs override
                   ) extends BinarySearchTree(weight)

case class LeafNode( char: Char
                   , override val weight: Int  //now needs override
                   ) extends BinarySearchTree(weight)

def createBST(inputFile: ListMap[Char,Int]): BinarySearchTree = {
  def weightOrder(t2: BinarySearchTree) = t2.weight

  val bst: BinarySearchTree = LeafNode('c',2) //build something of proper type

  val nodeMap:PriorityQueue[BinarySearchTree] =
    PriorityQueue(bst)(Ordering.by(weightOrder))  //create PriorityQueue

  null  //etc.
}

PriorityQueue 是可变的并且类型不变，所以如果你想要一个 PriorityQueue[BinarySearchTree] 那么构造函数参数必须是 BinarySearchTree 类型而不是派生类型（即节点）。

按非大小写字段排序 PriorityQueue class

Ordering a PriorityQueue by a field of a non-case class

scala

priority-queue