Aviral GargA small code change can preserve the algorithm's syntax while invalidating its argument for correctness. Heap-based merging offers a useful example because the key precondition is easy to overlook.
To merge several ascending streams, keep their current heads in a min-heap. The smallest head is safe to emit because every unseen value in its stream is at least as large, and every other stream begins at a value at least as large as its own head. The heap stores a frontier of candidates whose ordering is justified by the ordering inside each stream.
Changing the key to select the largest head changes only one part of that argument. If the input streams are still ascending, larger values remain hidden behind smaller heads. The largest visible candidate need not be the largest remaining value.
Take the hypothetical inputs [2, 9] and [4, 8]. A max-heap of their heads chooses 4 while 9 is still hidden in the first stream. This cannot produce a globally descending merge. To merge in descending order using the same frontier method, each input stream must expose its largest remaining value first.
The desired output order and the input order are therefore separate requirements. Descending inputs can use a max-heap. Ascending inputs can be merged in ascending order and then reversed when the representation and memory constraints permit. Choosing among those approaches requires the actual preconditions, not just a request to “make it descending.”
The Python heapq documentation describes heap operations and sorted-stream merging. The underlying lesson extends beyond a particular library: a data structure gives guarantees about the elements placed into it. It cannot establish a relationship between those elements and values that the algorithm has not exposed.
The invariant also explains the complexity bound. With at most one head per stream in the heap, each emitted element requires a heap operation over at most k candidates. Scanning k input streams and using heapify to build the initial heap takes O(k) time. For N total elements, the resulting bound is O(k + N log(k + 1)) time and O(k) auxiliary heap space. This includes empty streams and assumes the inputs already satisfy the required ordering.
Node ownership introduces another requirement. Reusing linked-list nodes changes the original structure; copying values does not. An AI assistant that combines an ordering change with a node-reuse optimization can alter behavior the user never asked to change. Shared nodes or cyclic inputs require still more care. State the ownership contract before optimizing it.
A compact test set should distinguish ascending input, descending input, duplicate values, empty streams and a violated ordering precondition. Expected outputs should follow the declared contract. Testing only an example that happens to fit the new heap key can leave the mistaken assumption untouched.
For further study, write the sentence that justifies emitting the current heap root before writing the code. Then ask which property of the inputs makes that sentence true. That proof often exposes an ambiguous requirement faster than another round of generated implementation.