A cpp solution with priority queue, and questions.


  • 1
    R

    Here is my cpp solution with priority queue. My question is in the lines of code.

     class Solution {
        	struct CompareNode {
        	    bool operator()(ListNode* const & p1, ListNode* const & p2) {
        	        // return "true" if "p1" is ordered before "p2", for example:
        	        return p1->val > p2->val;
                   //Why not p1->val <p2->val; ??
        	    }
        	};
        public:
            ListNode *mergeKLists(vector<ListNode *> &lists) {
        
            	ListNode dummy(0);
            	ListNode* tail=&dummy;
        
            	priority_queue<ListNode*,vector<ListNode*>,CompareNode> queue;
        
            	for (vector<ListNode *>::iterator it = lists.begin(); it != lists.end(); ++it){
            		if (*it)
            		queue.push(*it);
            	}
            	while (!queue.empty()){
            		tail->next=queue.top();
            		queue.pop();
            		tail=tail->next;
        
            		if (tail->next){
            			queue.push(tail->next);
            		}
            	}
        
            	return dummy.next;
            }
        };

  • 4
    B

    That is because the priority_queue behaves as max-heap. In order to get it to behave as min-heap (so the the min element is at the top of the heap), you need to flip the '<' to '>' in the functor.


  • 0
    R

    The order is from the left to the root?


  • 0
    B

    Not sure if I understand what you mean by "left to root".
    I was saying that the priority queue is implemented as a (max) heap (so not a linked list or queue for that matter). When you pop from the top of max heap, you get the largest element. It uses the functor you provided to compare/order the elements.

    If you flip the comparator, you fool the max heap into becoming a min-heap, ie top of the heap becomes the min element. So when you pop elements from a min heap you will see them in ascending order.

    Hope this clarifies.


  • 0
    T

    Good solution.

    What is the time complexity for this?
    Looks like it is still nlogm, which is the same with the merge sort. Correct?


Log in to reply
 

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