MofuSpec.scala

class MofuSpec extends WordSpec with GeneratorDrivenPropertyChecks {
  def measure(seq: Seq[Int], heap: Heap[Int]): Unit = {
    val h = seq.foldLeft(heap) { (h, x) => h.insert(x) }
    val h2 = seq.foldLeft(h) { (h, x) => h.deleteMin() }
    assert(h2.isEmpty)
  }

  "mofu" should {
    "fumo" in {
      val initial = 300000
      val cases = Seq(initial, initial * 2, initial * 4, initial * 8)

      //val factory = LeftistHeap
      val factory = PairingHeap

      // warm up のつもり
      measure(1 to cases.last, factory.empty)

      cases.foreach { i =>
        val seq = (1 to i).map(_ => Random.nextInt())
        //val seq = 1 to i
        //val seq = (1 to i).reverse
        //val heap = LeftistHeap(seq: _*)
        //val queue = Queue(seq: _*)
        //val deque = Deque(seq: _*)

        val start = System.currentTimeMillis()

        measure(seq, factory.empty)
        //heap ++ seq

        println(System.currentTimeMillis() - start)
      }

      fail()
    }
  }
}

PairingHeap.scala

@SerialVersionUID(6347333177234854462L)
sealed abstract class PairingHeap[A](implicit protected[this] val ord: Ordering[A])
  extends Heap[A]
  with Heap.Meldable[A, PairingHeap]
  with Serializable {

  final override def orderedCompanion: GenericOrderedCompanion[PairingHeap] = PairingHeap

  final override protected[this] def newBuilder: mutable.Builder[A, PairingHeap[A]] = {
    PairingHeap.newBuilder
  }

  final override def findMin: A = this match {
    case Branch(v, _) => v
    case Leaf() => throw new NoSuchElementException("This heap is empty.")
  }

  // 本のやつだとスタオバするので書き換えた。
  // 1. リストの要素をマージ
  // 2. マージ結果を畳み込んで1つの ParingHeapに
  final override def deleteMin(): PairingHeap[A] = {
    @tailrec
    def mergePairs(heaps: List[Branch[A]], paired: List[PairingHeap[A]]): List[PairingHeap[A]] = {
      heaps match {
        case Nil => paired
        case h :: Nil => h :: paired
        case h1 :: h2 :: hs => mergePairs(hs, h1.meld(h2) :: paired)
      }
    }

    this match {
      case Leaf() => throw new NoSuchElementException("This heap is empty.")
      case Branch(_, Nil) => Leaf()
      case Branch(_, heaps) =>
        mergePairs(heaps, Nil).foldLeft[PairingHeap[A]](Leaf()) { (acc, pair) => acc.meld(pair) }
    }
  }

  final override def meld(that: PairingHeap[A]): PairingHeap[A] = (this, that) match {
    case (Leaf(), h) => h
    case (h, Leaf()) => h
    case (Branch(v1, hs1), h2 @ Branch(v2, _)) if v1 <= v2 => Branch(v1, h2 :: hs1)
    case (h1 @ Branch(_, _), Branch(v2, hs2)) => Branch(v2, h1 :: hs2)
  }
}

object PairingHeap extends OrderedTraversableFactory[PairingHeap] {
  implicit def canBuildFrom[A: Ordering]: CanBuildFrom[Coll, A, PairingHeap[A]] = {
    new GenericCanBuildFrom[A]()
  }

  override def newBuilder[A](implicit ord: Ordering[A]): mutable.Builder[A, PairingHeap[A]] = {
    ArrayBuffer.empty[A].mapResult { buffer =>
      buffer.foldLeft[PairingHeap[A]](Leaf()) { (acc, x) => acc.meld(Branch(x, Nil)) }
    }
  }

  @SerialVersionUID(6697530614353255528L)
  private final case class Leaf[A: Ordering]() extends PairingHeap[A] {
    override def isEmpty: Boolean = true
  }

  @SerialVersionUID(8881977291093735346L)
  private final case class Branch[A: Ordering](value: A,
                                               heaps: List[Branch[A]]) extends PairingHeap[A] {
    override def isEmpty: Boolean = false
  }
}