current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 5 down vote favorite

Please review my answer for this interview question: Merge k sorted arrays, using min heap.

import java.util.*;
public class MinHeap{    
 public static class HeapItem implements Comparable<HeapItem>{               
      int[] array;                
      int index;        // the index of current element               
      public HeapItem(int[] arr, int index) {
           array = arr;
           index = 0;
      }   
      @Override
      public int compareTo(HeapItem h){
          if(array[index] > h.array[h.index]){
              return 1;
          }else if(array[index] < h.array[h.index]){
              return -1;
          }else{
              return 0;
          }
      }
 }
 public static List<Integer> mergeArrays(int[][] arrays) {
      if (arrays == null || arrays.length == 0) {
          throw new IllegalArgumentException("Invalid input!");
      }     
      // priority queue is heap in Java
      PriorityQueue<HeapItem> pq = new PriorityQueue<HeapItem>();             
      // add arrays to the heap
      for (int i = 0; i < arrays.length; i++) {
          pq.add(new HeapItem(arrays[i], 0));
      }
      List<Integer> result = new ArrayList<Integer> ();       
      while (!pq.isEmpty()) {             
          HeapItem current = pq.remove();
          result.add(current.array[current.index]);                       
          if (current.index < current.array.length-1) {  
             pq.add(new HeapItem(current.array, current.index+1)); 
          }
     }
     return result;
 }          
 public static void main(String[] args){
     int[] arr1 = {1, 3, 5, 7};
     int[] arr2 = {2, 4, 6, 8};
     int[] arr3 = {0, 9, 10, 11};        
     System.out.println(mergeArrays(new int[][] {arr1, arr2, arr3}));
 }
}
share|improve this question
    
Did you try running this code? – Misha Aug 16 '15 at 2:58
    
@Misha, sorry, as @JS1 mentioned, mistakenly I assigned zero to index. If replace index = 0; by this.index = index; it works. I'll edit it. – Hengameh Aug 16 '15 at 3:26
    
What about reducing merge over the array of sorted arrays? It looks simpler to me – Caridorc Aug 16 '15 at 9:48
    
@Caridorc How we can merge k arrays? Using stack or queue or some data structure, you mean? – Hengameh Aug 16 '15 at 10:05
1  
Reducing means applying the function repeadeatly with two args, an accumulator and a new value. Merging k arrays may be arrays.reduce(merge). While simpler I fear time complexity may be worse – Caridorc Aug 16 '15 at 10:08
up vote 6 down vote

Bug

This might be a typo, but when I ran your program it infinitely looped. The problem was in your constructor:

  public HeapItem(int[] arr, int index) {
       array = arr;
       index = 0;
  }

Here, you are setting index to 0 when you should be setting it to the input argument, like this:

  public HeapItem(int[] arr, int index) {
       array = arr;
       this.index = index;
  }

Reuse HeapItem

Your code all seemed very reasonable to me. There is just one small improvement I would make here:

      if (current.index < current.array.length-1) {  
         pq.add(new HeapItem(current.array, current.index+1)); 
      }

I would just reuse current instead of creating a new HeapItem, like this:

      if (current.index < current.array.length-1) {
         current.index++;
         pq.add(current); 
      }

Create result list with exact size

One other small thing you could do is compute the output list size, when you are iterating through the arrays. That way, you could create result with the correct size instead of having it autoexpand as you add elements to it.

  int outputSize = 0;
  for (int i = 0; i < arrays.length; i++) {
      pq.add(new HeapItem(arrays[i], 0));
      outputSize += arrays[i].length;
  }
  List<Integer> result = new ArrayList<Integer> (outputSize);
share|improve this answer
    
Thanks for your comments. I also edited that bug you have mentioned :) – Hengameh Aug 16 '15 at 3:36
up vote 0 down vote

I suggest implementing merging an array of arrays as reducing merge over them. The implementation will be substantially simpler than yours but I fear time complexity may be worse.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.