Big(O) of finding K element in a MinHeap build from 2 unsorted arrays

Question

Given the question here. https://www.careercup.com/question?id=9406769 which asks: Given two unsorted int arrays, find the kth element in the merged, sorted array. k element in an index that starts at 1.

What would be the BigO performance of the solution below (prints 1):

    object MergeTwoArraysFindK {

  import scala.collection.mutable.PriorityQueue

  def findK(arrayOne: Array[Int], arrayTwo: Array[Int], k: Int): Int = {
    implicit val ord = Ordering[Int].reverse
    val minHeap = new PriorityQueue[Int] ++= (arrayOne ++ arrayTwo).iterator
    for (i <- 1 to k)
      if (i == k)
        return minHeap.dequeue()
      else
        minHeap.dequeue()
    -1
  }

  def main(args: Array[String]): Unit = {
    val arrayOne = Array[Int](3, 4, 9, 0, 1, 2, 4)
    val arrayTwo = Array[Int](5, 4, 1, 0, 9, 8)
    println(findK(arrayOne, arrayTwo, 4))
  }
}

Where are you stuck? Do you know the big-O of your operations? (add to queue, dequue, etc)? — The Archetypal Paul, Feb 11 '17 at 19:56
BTW, you might want a bounded priority queue. See http://stackoverflow.com/questions/7878026/is-there-a-priorityqueue-implementation-with-fixed-capacity-and-custom-comparato — The Archetypal Paul, Feb 11 '17 at 20:00
I think the answer should be O(n) for the time searching the heap. Now the complete time I believe it should include building the heap by merging the two arrays into the heap which it is probably n + O(log n). Where n should be the concatenation of the arrays and O(log n) is the insertion. Am I right? — Fabio, Feb 14 '17 at 07:31

score 0 · Accepted Answer · edited May 23 '17 at 10:29

0

It takes O(n) time to build the heap, and it requires O(n) extra space.

Finding the kth item is O(k log n) Each call to minheap.dequeue requires O(log n), and you're making k calls.

This approach works if you have enough memory to hold everything in memory. If you don't have enough memory, say you're doing this with two absolutely huge files, then the process is slightly different. See Time complexity of Kth smallest using Heap.

edited May 23 '17 at 10:29

Community

1
1

answered Feb 14 '17 at 14:52

Jim Mischel

131,090
20
188
351

Just the clear answer that I was looking for, thanks. – Fabio Feb 16 '17 at 17:23
So according to your answer O(k log n) == K * O(n) ? – Fabio Feb 16 '17 at 17:56
@Fabio: Thank you for pointing out my error. See the correction. Each call to `minheap.dequeue` requires O(log n). – Jim Mischel Feb 16 '17 at 17:58

Big(O) of finding K element in a MinHeap build from 2 unsorted arrays

1 Answers1