merge_k_sorted_lists_with_heap.cpp

/*
 * =====================================================================================
 *
 *       Filename:  merge_k_sorted_lists_with_heap.cpp
 *
 *    Description:  https://leetcode.com/submissions/detail/29638723/
 *
 *        Version:  1.0
 *        Created:  06/08/2015 03:07:49 PM
 *       Revision:  none
 *       Compiler:  gcc/g++
 *
 *         Author:  Marius-Constantin Melemciuc  
 *          email:  
 *   Organization:  
 *
 * =====================================================================================
 */

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {
    }
};
 

// O(NlogK)     N = the total number of numbers in all k lists 
class Solution {
    vector<pair<int, int> > heap;            // 1st = element, 2nd = the array from which is the element
public:
    void swap(pair<int, int>& a, pair<int, int>& b) {
        pair<int, int> aux = a;
        a = b;
        b = aux; 
    }
    
    void minHeapifyDown(int index, int nr) {
        int left, right, x = index;
        
        left  = index << 1;
        right = left + 1;
        
        if (left <= nr && heap[left].first < heap[index].first)
            x = left;
        if (right <= nr && heap[right].first < heap[x].first) 
            x = right;
        if (x != index) {
            swap(heap[index], heap[x]);
            minHeapifyDown(x, nr);
        }
    }
    
    pair<int, int> getMinFromHeap() {
        return heap[1];
    }
    
    void popFromHeap(int& nr) {
    	heap[1] = heap[nr];
    	nr--;
    	minHeapifyDown(1, nr);
    }
    
    void buildMinHeap(int nr) {         // linear time
        for (int i = (nr >> 1); i >= 1; i--) 
            minHeapifyDown(i, nr);
    }
    
    void heapSortNonAscendingOrder(int n) {   // O(NlogN)
        int nr = n;
        
        for (int i = n; i >= 2; i--) {
            swap(heap[1], heap[i]);
            nr--;
            minHeapifyDown(1, nr); // maxHeapifyDown(1, nr);   for sorting in ascending order
        }
    }
    
    // O(N * log K)      N = the total number of numbers, K = the number of sorted lists
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() < 1)
            return NULL;
            
        vector<int> result; 
        
        for (int i = 0; i <= lists.size(); i++) 
            if (lists[i] != NULL)
                heap.push_back(make_pair(0, 0));
        
        if (heap.size() < 1)
            return NULL;
        
        // insert in the heap the first k elements, 
        // one from each sorted list, the first element from each sorted list 
        int k = 0;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != NULL) {
                pair<int, int> element = make_pair(lists[i]->val, i);
                k++;
                heap[k] = element;
                if (lists[i] != NULL)
                    lists[i] = lists[i]->next;
            }
        }
        
        buildMinHeap(k);
        
        bool has_elements = true;
        while (has_elements) {
            pair<int, int> element = getMinFromHeap();
            int value = element.first;
            int which_list = element.second;
            
            result.push_back(value);
            pair<int, int> next_element; 
            if (lists[which_list] != NULL) {
            	next_element = make_pair(lists[which_list]->val, which_list); 
            } else {
            	has_elements = false;
                int i; 
                for (i = 0; i < lists.size() && !has_elements; i++) 
                    if (lists[i] != NULL) 
                        has_elements = true;
                if (has_elements) {
                	i--;
                	next_element = make_pair(lists[i]->val, i);
                }
            }
            if (has_elements) {
           	heap[1] = next_element;
           	if (lists[next_element.second] != NULL) 
           	    lists[next_element.second] = lists[next_element.second]->next;
            	minHeapifyDown(1, k);
            } else {
	        popFromHeap(k); // to remove the first element, it was inspected from getMinFromHeap() 
            }
        }
        
	//sort the ones remaining, from heap
	heapSortNonAscendingOrder(k);
		
	// put the rest of the k elements in the result
	for (int i = k; i >= 1; i--)
	    result.push_back(heap[i].first); 
        
        ListNode* root = new ListNode(0);
        if (result.size() < 1)
            return NULL;
        ListNode* result_list = root;
        root->val = result[0];
        root->next = NULL;
        for (auto it = result.begin() + 1; it != result.end(); it++) {
            ListNode* tmp = new ListNode(0);
            tmp->val = *it;
            tmp->next = NULL;
            root->next = tmp;
            root = tmp;
        }
        
        return result_list;
    }
};

int main() {
    vector<ListNode*> lists;
    int k;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif 
    cin >> k;

    for (int i = 0; i < k; i++) {
        int num; 
        cin >> num;
        
        if (num < 1)
        	continue;
        int y; 
        cin >> y;
        ListNode* root = new ListNode(y);
        ListNode* first = root;
        for (int j = 1; j < num; j++) {
            int x;
            cin >> x;
            ListNode* tmp = new ListNode(0);
            tmp->val = x;
            tmp->next = NULL;
            root->next = tmp;
            root = tmp;    
        }
        lists.push_back(first);
    }

    Solution t;
    
    ListNode* root = t.mergeKLists(lists);
    
    while (root != NULL) {
    	cout << root->val << " ";
    	root = root->next;
    }
	
    return 0;
}

input.txt

3
2
-1 1
3
-3 1 4
4
-2 -1 0 2

input.txt

7
7
-10 -9 -9 -3 -1 -1 0
1
-5
1
4
1
-8
0
7
-9 -6 -5 -4 -2 2 3
5
-3 -3 -2 -1 0