CODEWITHSUNDEEP
c++algorithmsortingdata-structures
Amit
Amit

Reputation: 3

Can anyone explain how custom comparator works in C++?

Ques: Given an array of linked-lists lists, each linked list is sorted in ascending order. Merge all the linked-lists into one sort linked-list and return it.

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

I don't understand how this custom comparator is working for min-heap priority_queue.

/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, comp> pq;
        for(auto head : lists){
            if(head != NULL)
                pq.push(head);
        }
        ListNode* dummy = new ListNode(-1);
        ListNode* curr = dummy;
        while(!pq.empty()){
            curr->next = pq.top();
            pq.pop();
            curr = curr->next;
            ListNode* next = curr->next;
            if(next != NULL)
                pq.push(next);
        }
        return dummy->next;
    }
    
    struct comp{
        bool operator()(ListNode* a, ListNode* b){
            return a->val > b->val;
        }  
    };
};

Why the return val is a->val > b->val instead of a->val < b->val

Upvotes: 0

Views: 292

Answers (1)

Bill Lynch
Bill Lynch

Reputation: 81926

std::priority_queue is documented on cppreference with:

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater<T> would cause the smallest element to appear as the top().

So if you want to have a priority queue where you can pop the smallest element, it expects you to pass a comparator that returns true if a > b.

(And note that you're leaking the object allocated at dummy)

Upvotes: 1

Related Questions