How to ensure O(log n) insert complexity without loops ?

Loops are widely used in programming. We use them to iterate through the elements of one collection or to implement a sorting algorithm like in the following snippet:

  behavior of "priority queue"

  it should "be implemented naively with a for loop and ordering" in {
    def addLetter(letter: String, data: List[String]): List[String] = {
      var wasSplitted = false
      var splitIndex = -1
      for (index <- 0 until data.length if !wasSplitted) {
        val letterFromData = data(index)
        if (letter > letterFromData) {
          wasSplitted = true
          splitIndex = index
        }
      }
      val (splittedListBeginning, splittedListEnd) = data.splitAt(splitIndex)
      val prioritizedList = splittedListBeginning ++ List(letter) ++ splittedListEnd
      prioritizedList
    }

    val prioritizedList = addLetter("A", List.empty)
    val prioritizedListWithD = addLetter("D", prioritizedList)
    val prioritizedListWithB = addLetter("B", prioritizedListWithD)

    prioritizedListWithB should have size 3
    prioritizedListWithB should contain inOrder("D", "B", "A")
  }

However, Scala comes the data structure able to implement this sorting behavior without a loop. This structure is called PriorityQueue and below you can find an example:

  it should "use built-in data structure" in {
    val priorityLetters = new scala.collection.mutable.PriorityQueue[String]()

    priorityLetters.enqueue("A")
    priorityLetters.enqueue("D")
    priorityLetters.enqueue("B")

    priorityLetters should have size 3
    priorityLetters.dequeueAll should contain inOrder("D", "B", "A")
  }

  it should "use built-in data structure with custom ordering" in {
    case class Customer(businessValue: Int)
    //def compareCustomers(customers: (Customer, Customer)): Int = customers._1.businessValue > customers._2.businessValue
    //val customerOrdering: Ordering[Customer] = Ordering.by(customer => customer.businessValue)
    def getCustomerOrder(customer: Customer): Int = customer.businessValue

    val customers = new scala.collection.mutable.PriorityQueue[Customer]()(Ordering.by(getCustomerOrder))

    customers.enqueue(Customer(1))
    customers.enqueue(Customer(100))
    customers.enqueue(Customer(50))

    customers should have size 3
    customers.dequeueAll should contain inOrder(Customer(100), Customer(50), Customer(1))
  }