優先級隊列與自定義排序

我有這樣的情況下類：優先級隊列與自定義排序

case class Offer(id: Int, amount: Int, interestRate: Double) extends Ordered[Offer] { 

    def compare(that: Offer) = interestRate.compareTo(that.interestRate) 
}

正如你所看到的，我定義了基於Offer.interestRate排序。我希望訂單在增加。

我創造了這些提議：

Offer(1, 5, 4.0) 
Offer(2, 5, 0.5) 
Offer(3, 5, 1.5)

，並將它們添加到優先級隊列：

val currentOffers: mutable.PriorityQueue[Offer] = mutable.PriorityQueue.empty[Offer]

的問題是，當我做currentOffers.dequeue()我得到Offer(1, 5, 4.0)。

相反，我想獲得：

Offer(2, 5, 0.5)

我需要做什麼改變嗎？

來源

2016-09-06 octavian

正如其他人暗示沒有太多的解釋，問題是你的比較函數：

def compare(that: Offer) = this.interestRate.compareTo(that.interestRate)

這對於其中-1 1.

當你創建一個優先級隊列數的自然順序相匹配在Scala中，它使用了一個Ordering，它隱含地來自您定義的Order。你缺少的是，優先級隊列會將「高」值視爲具有最高優先級（基本上它按降序排列）。

這個最簡單的解決將是該compare功能改變它的逆：

def compare(that: Offer) = that.interestRate.compareTo(this.interestRate)

注that和this反轉。

另一種辦法是建立隊列時提供Ordering：

val q = mutable.PriorityQueue(
    Offer(1, 5, 4.0), 
    Offer(2, 5, 0.5), 
    Offer(3, 5, 1.5) 
)(Ordering.by[Offer, Double](_.interestRate).reverse)

這樣做的是：「通過排序反向利率創造提供了一個排序」。

我更喜歡第二個選項，因爲它提供了更好的粒度，並允許在必要時使用多個排序。

來源

2016-09-06 08:17:51

優先級隊列與自定義排序

回答

相關問題