CareerCup

Given k sorted lists, with the total of n elements.
keep a pointer to each of the list
construct a minheap (data and arraynumber) by taking the first element from all the arrays.
increment all the pointers by 1

extract the minelement and print
take the element from the array in which the min element in present, and insert to min heap.
increment that pointer.
Continue till all the pointers reach end and min heap becomes empty

It is O(NlogK) because there are logK merge operation of the external merge sort. At each you scan N elements.

This comment has been deleted.

kirubakaran :

but now how would the complexity be nlogk becoz u are accessing each element once
hence complexity becomes n.k

please correct me always hav a complexity issue

Basically u hav to pick the smallest element from all the arrays in the 1st position of the final array.
So for this reason the merge part of the merge-sort algorithm can be used.

O(NlogK) is correct .

Hey what is the complexity of getting next element from list of arrays? you need to search again which array contained the min element? anybody can answer?

import java.util.ArrayList;
import java.util.List;

public class MergeLists {

	public static class Node implements Comparable<Node> {

		int data;
		Node next;

		Node(int data){
			this.data = data;
		}
		@Override
		public int compareTo(Node o) {
			if (this.data == o.data) {
				return 0;
			} else if (this.data < o.data) {
				return -1;
			}
			return 1;
		}
	}

	private Node resultList;
	private MinHeap<Node> minHeap;

	
	public MergeLists(List<Node> lists) {
		
		this.minHeap = new MinHeap<Node>(lists.size(), lists);
		this.minHeap.buildHeap();
	}

	public void merge() {

		Node tail = null;
		while (!minHeap.isEmpty()) {

			Node node = minHeap.deleteMin();
			
			if (resultList == null) {
				resultList = node;
				tail = node;
			} else {
				tail.next = node;
				tail = node;
			}
			if (node.next != null) {
				minHeap.insert(node.next);
			}
			node.next = null;
		}
	}

	public static void main(String[] args) {
		
		List<Node> list = new ArrayList<MergeLists.Node>();
		Node n1 = new Node(1);
		n1.next = new Node(2);
		n1.next.next = new Node(3);
		n1.next.next.next = new Node(5);
		n1.next.next.next.next = new Node(7);
		list.add(n1);
		
		Node n2 = new Node(4);
		n2.next = new Node(6);
		n2.next.next = new Node(8);
		n2.next.next.next = new Node(10);
		list.add(n2);

		Node n3 = new Node(9);
		n3.next = new Node(11);
		n3.next.next = new Node(12);
		n3.next.next.next = new Node(13);
		list.add(n3);

		Node n4 = new Node(-4);
		n4.next = new Node(-2);
		n4.next.next = new Node(-1);
		n4.next.next.next = new Node(14);
		list.add(n4);

		Node n5 = new Node(-3);
		list.add(n5);
		
		MergeLists ml = new MergeLists(list);
		ml.merge();
		ml.printList();
	}

	private void printList() {
		
		Node temp = resultList;
		while(temp != null) {
			System.out.print(temp.data + ", ");
			temp = temp.next;
		}		
	}
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MinHeap<E extends Comparable<E>> {

	private List<E> elements;
	private int k;

	public MinHeap(int k, List<E> elements) {
		this.k = k;
		this.elements = elements;
	}

	public boolean isEmpty() {
		return k <= 0;
	}

	public void buildHeap() {
		for (int i = k / 2 - 1; i >= 0; i--) {
			heapify(i);
		}
	}

	public void heapify(int root) {

		int left = leftChild(root);
		int right = rightChild(root);
		int min = root;
		if (k > left && elements.get(root).compareTo(elements.get(left)) > 0) {
			min = left;
		}

		if (k > right && elements.get(min).compareTo(elements.get(right)) > 0) {
			min = right;
		}

		if (min != root) {
			swap(min, root);
			heapify(min);
		}

	}

	public void insert(E e) {
		elements.add(k++, e);
		int parent = parent(k - 1);
		int i = k - 1;
		while (parent >= 0
				&& elements.get(parent).compareTo(elements.get(i)) > 0) {
			swap(parent, i);
			i = parent;
			parent = parent(i);
		}
	}

	public E deleteMin() {
		swap(0, k - 1);
		k--;
		heapify(0);
		E e = elements.get(k);
		elements.remove(k);
		return e;
	}

	private void swap(int i, int j) {
		E temp = elements.get(i);
		elements.set(i, elements.get(j));
		elements.set(j, temp);
	}

	private int parent(int i) {
		return (i - 1) / 2;
	}

	private int leftChild(int i) {
		return 2 * i + 1;
	}

	private int rightChild(int i) {
		return 2 * i + 2;
	}

	public static void main(String[] args) {
		Integer[] elements = { 3, 2, 1, 5, 4, 0, 1, -1, -9 };

		ArrayList<Integer> elementList = new ArrayList<Integer>(
				Arrays.asList(elements));
		int k = elements.length;
		MinHeap<Integer> heap = new MinHeap<Integer>(k, elementList);
		heap.buildHeap();
		for (int e : elementList) {
			System.out.print(e + ", ");
		}

		System.out.println();
		System.out.println(heap.deleteMin());
		for (int e : elementList) {
			System.out.print(e + ", ");
		}
	}
}

The simple merge of every 2 arrays should be easier:

import java.util.ArrayList;
import java.util.List;

/**
 * @author Sabuj 
 *
 */
public class Merge {

	public static void main(String[] args) {
		List<Integer[]> arrays = new ArrayList<Integer[]>();
		arrays.add(new Integer[]{10, 15, 17, 20});
		arrays.add(new Integer[]{5, 7, 11, 19, 22});
		arrays.add(new Integer[]{1, 8, 12});
		
		Integer[] p = mergeArrays(arrays);
		for (int i = 0; i < p.length; i++) {
			System.out.print(p[i] + ", ");
		}
	}
	
	
	public static Integer[] mergeArrays(List<Integer[]> arrays){
		if(arrays == null || arrays.size() == 0)
			return null;
		Integer[] p, q;
		if(arrays.size() >= 2){
			p = arrays.get(0);
			for (int i = 1; i < arrays.size(); i++) {
				p = merge(p, arrays.get(i));
			}
		} else {
			return arrays.get(0);
		}
		return p;
	}
	
	public static Integer[] merge(Integer[] a, Integer[] b){
		Integer[] c = new Integer[a.length+b.length];
		int i=0, j=0, k=0;
		
		while(i < a.length && j < b.length){
			if(a[i] <= b[j])
				c[k++] = a[i++];
			else
				c[k++] = b[j++];
		}
		
		while(i < a.length)
			c[k++] = a[i++];
		
		while(j < b.length)
			c[k++] = b[j++];
		
		
		return c;
	}
	
}

merge k sorted lists: writeulearn.com/leetcode-merge-sorted-lists/