C++合并K个有序链表中priority_queue自定义比较器的原理疑问

Great question! Let's walk through exactly why the comparator uses a->val > b->val instead of the more intuitive a->val < b->val—it all boils down to how C++'s priority_queue works under the hood.

First, How Default priority_queue Behaves #

By default, a priority_queue in C++ is a max-heap. That means it always keeps the largest element at the top (so pq.top() returns the biggest value). The default comparator is std::less<T>, which tells the heap: "If a < b is true, then b has higher priority than a and should come before it." This is why the largest element ends up on top.

What We Need for Merging Sorted Lists #

Our goal here is to always grab the smallest available node from all the linked lists, so we can build the merged list in ascending order. To do this, we need a min-heap instead of a max-heap—where the smallest element is at the top.

How the Custom comp Comparator Creates a Min-Heap #

The comp struct's operator() function is our way of redefining "priority" for the heap. Let's break down its logic:

bool operator()(ListNode* a, ListNode* b){
    return a->val > b->val;
}

This function returns true when a's value is greater than b's value. For the priority_queue, returning true here means: "a has lower priority than b—so put b above a in the heap."

Let's use an example from your input: say we have nodes with values 4 and 1. When we pass these to comp(), 4 > 1 is true, so the heap knows that the node with value 4 should be placed below the node with value 1. This puts the smallest node at the top of the heap, which is exactly what we need for our merge logic.

What Happens If We Used a->val < b->val? #

If we swapped the comparator to return a->val < b->val, we'd be replicating the default std::less<T> behavior. This would create a max-heap, so pq.top() would return the largest node every time. Our merged list would end up in descending order, which is the opposite of what the problem requires.

Recap of the Code's Logic #

To tie it all together:

• We start by pushing the non-null head of each linked list into the min-heap.
• We then repeatedly take the smallest node from the heap (using pq.top()), append it to our merged list, and push that node's next element (if it exists) back into the heap.
• This process continues until the heap is empty, resulting in a fully merged sorted linked list.

内容的提问来源于stack exchange，提问作者Amit