C++ code O(NKlogK) with a easy handmade implementation of heap


  • 1
    L

    Its time complexity is O(NKlogK), N is the length of a list, K is the number of lists
    In this code, it merges K lists at the same time.
    for comparison,
    if merge one list at a time and merge K-1 times, time is 2N+3N+...+KN = O(NK^2)
    if use the way similar to merge sort, time is also O(NKlogK)

    	void adjust_down(int i, int n, vector<ListNode*>& heap) {
    		int t;
    		while ((t = 2 * i + 1) < n) {
    			if (t + 1 < n && heap[t]->val > heap[t + 1]->val)
    				++t;
    			if (heap[t]->val < heap[i]->val) {
    				ListNode* temp = heap[i];
    				heap[i] = heap[t];
    				heap[t] = temp;
    				i = t;
    			}
    			else break;
    		}
    	}
    
    	ListNode* mergeKLists(vector<ListNode*>& lists) {
    		ListNode headnode(-1);
    		ListNode* merged = &headnode;
    		vector<ListNode*> heap(lists.size());
    		int hsize = 0;
    		for (int i = 0; i < lists.size(); i++)
    			if (lists[i])
    				heap[hsize++] = lists[i];
    
    		for (int i = hsize / 2 - 1; i >= 0; i--)//construct a heap
    			adjust_down(i, hsize, heap);
    
    		while (hsize) {
    			merged->next = heap[0];
    			merged = merged->next;
    			heap[0] = heap[0]->next;
    			if (!heap[0])
    				heap[0] = heap[--hsize];
    			adjust_down(0, hsize, heap);
    		}
    		return headnode.next;
    	}
    

Log in to reply
 

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