Java log(nlogk) Using Heap (priority queue)


  • 0
    M
    package problems;
    
    import java.util.Comparator;
    import java.util.PriorityQueue;
    import java.util.Queue;
    
    import structures.ListNode;
    
    public class MergeKSortedList {
    	@SuppressWarnings("null")
    	public ListNode mergeKLists(ListNode[] lists) {
    		if (lists == null && lists.length == 0) {
    			return null;
    		}
    
    		Queue<ListNode> q = new PriorityQueue<ListNode>(20,
    				new Comparator<ListNode>() {
    					public int compare(ListNode l1, ListNode l2) {
    						if (l1.val < l2.val)
    							return -1;
    						else if (l1.val > l2.val)
    							return 1;
    						else
    							return 0;
    					}
    				});
    
    		for (int i = 0; i < lists.length; i++) {
    			if (lists[i] != null) {
    				q.add(lists[i]);
    			}
    		}
    
    		ListNode dummy = new ListNode(0);
    		ListNode root = dummy;
    
    		while (!q.isEmpty()) {
    
    			dummy.next = q.poll();
    			dummy = dummy.next;
    			if (dummy.next != null) {
    				q.add(dummy.next);
    			}
    			dummy.next = null;
    		}
    
    		return root.next;
    	}
    }

  • 0
    L

    Unfortunately, the complexity of the proposed heap-based algorithm is still O(nklog(k)).

    1. As you can see, in the while loop, the step of adding an element to the priority queue is "q.add(dummy.next)". This step requires O(log(k)) time complexity, which is the time required in heap adjustment.

    2. We can expect that the while loop will run O(n*k) times to put all nodes from k lists into the final sorted list.

    3. Based on the observations from 1 and 2, we can easily conclude that the actual time complexity is O(nklog(k)) for the algorithm.


  • 0
    M
    I don't agree with your analysis. Below is my analysis
    
    Assuming priority queue built using Heap
    1. Complexity of initial heap of size k = O(k).
    2. HEAPIFY takes O(logk)
    3. (n-k) times it needs to be Heapfy.
    
    So complexity would be 
    
    =>O(k) + O((n-k)*logk)
    =>O(k) + O(nlogk)-o(klogk)
    => O(nlogk).

  • 0
    D

    I don't know why you still need to add the dummy.next back to the q? I think you have already add this element in the for loop.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.