A sorted map that sorts keys by value

ValueSortedMap.scala

import scala.collection.mutable

type PQ[K, V] = mutable.SortedMap[K, V]
object PQ {

  def apply[K, V: Ordering](elems: Seq[(K, V)]): PQ[K, V] =
    elems.foldLeft(PQ.empty[K, V])(_ += _)

  /**
    * A SortedMap which sorts keys by the value
    * When a key is updated with a new value, node is automatically re-prioritized
    *
    * get/contains is O(1); add, remove, update, first, last, removeFirst, removeLast are O(log n)
    */
  def empty[K, V: Ordering]: PQ[K, V] = new mutable.SortedMap[K, V] {
    private val valueMap = mutable.Map.empty[K, V]
    private val delegate = mutable.SortedMap.empty[K, V]

    override def +=(kv: (K, V)) = {
      this -= kv._1
      valueMap += kv
      delegate += kv
      this
    }

    override def -=(key: K) = {
      if(contains(key)) {
        delegate -= key
        valueMap -= key
      }
      this
    }

    override implicit def ordering = Ordering.by(valueMap)

    override def get(key: K) = valueMap.get(key)

    override def valuesIteratorFrom(start: K) = delegate.valuesIteratorFrom(start)
    override def rangeImpl(from: Option[K], until: Option[K]) = delegate.rangeImpl(from, until)
    override def iteratorFrom(start: K) = delegate.iteratorFrom(start)
    override def keysIteratorFrom(start: K) = delegate.keysIteratorFrom(start)
    override def iterator = delegate.iterator
  }
}

ValueSortedMap_Scala211.scala

 /**
    * Prior to Scala 2.12, we did not have mutable.SortedMap so we use this one
    * Same complexity as above except for last is O(n) instead of O(log n)
    */
  def newValueSortedMap[K, V: Ordering] = new mutable.Map[K, V] {
    private val valueMap = mutable.Map.empty[K, V]
    private val delegate = mutable.SortedSet.empty[K](Ordering.by(valueMap))

    override def +=(kv: (K, V)) = {
      this -= kv._1
      valueMap += kv
      delegate += kv._1
      this
    }

    override def -=(key: K) = {
      if(contains(key)) {
        delegate -= key
        valueMap -= key
      }
      this
    }

    override def get(key: K) = valueMap.get(key)

    override def iterator = delegate.iterator.map(k => k -> valueMap(k))
  }