fork download

//Merge K Sorted Lists
 
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
 
class node{
public:
    int data;
    node* next;
 
    node(int d) {
        data = d;
        next = NULL;
    }
};
 
void insertAtTail(node* &head, int data){
    //if there is no data 
    if(head == NULL){
        head = new node(data);
        return;
    }
 
    //otherwise need to find tail point
    node*tail = head;
    while(tail->next != NULL){
        tail = tail->next;
    }
    tail->next = new node(data);
    return;
}
 
void printList(node *head) {
    while(head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}
 
// Comparison object to be used to order the min-heap
class compare{
    bool operator() (node *lhs, node *rhs) {
        return lhs->data < rhs->data;
    }
};
 
 
// The main function to merge given `k` sorted linked lists.
// It takes array `lists` of size `k` and generates the sorted output
node *mergeKSortedList(vector<node *> &lists) {
 
    //create a empty min heap
    priority_queue<node*, vector<node* >, compare> pq;
 
    // push the first node of each list into the min-heap
    for (node* list: lists) {
        pq.push(list);
    }
 
    // take two pointers, head and tail, where the head points to the first node
    // of the output list and tail points to its last node
    node *head = NULL;
    node *last = NULL;
 
    // run till min-heap is empty
    while (!pq.empty())
    {
        // extract the minimum node from the min-heap
        node* min = pq.top();
        pq.pop();
 
        // add the minimum node to the output list
        if (head == NULL) {
            head = last = min;
        }
        else {
            last->next = min;
            last = min;
        }
 
        // take the next node from the "same" list and insert it into the min-heap
        if (min->next != NULL) {
            pq.push(min->next);
        }
    }
    // return head node of the merged list
    return head;
}
 
int main() {
 
    int k;
    int n;
 
    cin >> k >> n;
 
    // an array to store the head nodes of the linked lists
    vector<node *> lists(k); 
 
    //input
 
    node *head = mergeKSortedList(lists);
    printList(head);
    return 0;
}

In file included from /usr/include/c++/8/bits/stl_algobase.h:71,
                 from /usr/include/c++/8/bits/char_traits.h:39,
                 from /usr/include/c++/8/ios:40,
                 from /usr/include/c++/8/ostream:38,
                 from /usr/include/c++/8/iostream:39,
                 from prog.cpp:3:
/usr/include/c++/8/bits/predefined_ops.h: In instantiation of ‘bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<node**, std::vector<node*> >; _Value = node*; _Compare = compare]’:
/usr/include/c++/8/bits/stl_heap.h:133:48:   required from ‘void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<node**, std::vector<node*> >; _Distance = long int; _Tp = node*; _Compare = __gnu_cxx::__ops::_Iter_comp_val<compare>]’
/usr/include/c++/8/bits/stl_heap.h:207:23:   required from ‘void std::push_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<node**, std::vector<node*> >; _Compare = compare]’
/usr/include/c++/8/bits/stl_queue.h:610:16:   required from ‘void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = node*; _Sequence = std::vector<node*>; _Compare = compare; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = node*]’
prog.cpp:60:21:   required from here
/usr/include/c++/8/bits/predefined_ops.h:177:11: error: ‘bool compare::operator()(node*, node*)’ is private within this context
  { return bool(_M_comp(*__it, __val)); }
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
prog.cpp:45:10: note: declared private here
     bool operator() (node *lhs, node *rhs) {
          ^~~~~~~~
In file included from /usr/include/c++/8/bits/stl_algobase.h:71,
                 from /usr/include/c++/8/bits/char_traits.h:39,
                 from /usr/include/c++/8/ios:40,
                 from /usr/include/c++/8/ostream:38,
                 from /usr/include/c++/8/iostream:39,
                 from prog.cpp:3:
/usr/include/c++/8/bits/predefined_ops.h: In instantiation of ‘constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<node**, std::vector<node*> >; _Iterator2 = __gnu_cxx::__normal_iterator<node**, std::vector<node*> >; _Compare = compare]’:
/usr/include/c++/8/bits/stl_heap.h:222:14:   required from ‘void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<node**, std::vector<node*> >; _Distance = long int; _Tp = node*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<compare>]’
/usr/include/c++/8/bits/stl_heap.h:253:25:   required from ‘void std::__pop_heap(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<node**, std::vector<node*> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<compare>]’
/usr/include/c++/8/bits/stl_heap.h:320:19:   required from ‘void std::pop_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<node**, std::vector<node*> >; _Compare = compare]’
/usr/include/c++/8/bits/stl_queue.h:645:15:   required from ‘void std::priority_queue<_Tp, _Sequence, _Compare>::pop() [with _Tp = node*; _Sequence = std::vector<node*>; _Compare = compare]’
prog.cpp:73:16:   required from here
/usr/include/c++/8/bits/predefined_ops.h:143:18: error: ‘bool compare::operator()(node*, node*)’ is private within this context
         { return bool(_M_comp(*__it1, *__it2)); }
                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
prog.cpp:45:10: note: declared private here
     bool operator() (node *lhs, node *rhs) {
          ^~~~~~~~

Standard output is empty