Блог

Вопрос: Учитывая массив списков связанных списков, каждый связанный список сортируется в порядке возрастания. Объедините все связанные списки в один сортированный связанный список и верните его.

 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
  

Я не понимаю, как этот пользовательский компаратор работает для 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*>amp; 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;
        }  
    };
};
  

Почему возвращаемое значение a->val > b->val вместо a->val < b->val

std::priority_queue задокументирован в cppreference с:

Для изменения порядка может быть предоставлено пользовательское сравнение, например, использование std::greater<T> приведет к тому, что наименьший элемент будет отображаться как top() .

Поэтому, если вы хотите иметь приоритетную очередь, куда вы можете поместить наименьший элемент, он ожидает, что вы передадите компаратор, который возвращает true, если a > b .

(И обратите внимание, что вы пропускаете объект, выделенный в dummy )