Input invariants in generated algorithms

“Make the merge descending” sounds like a change to the heap key. With ascending inputs [2, 9] and [4, 8], the largest visible head is 4. The required first value is 9. The max-heap can be correct while the algorithm is wrong.

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.

The frontier determines which value the heap can choose:

The max-heap is working correctly in both rows. The first algorithm is wrong because the heap never received the hidden 9. To merge in descending order using this frontier method, every stream must expose its largest remaining value first.

Output order, input order and access constraints are separate requirements. Descending inputs can use a max-heap. Ascending arrays can be traversed from their ends without reversing their contents. A one-pass ascending stream cannot reveal its largest value until its end. To emit every value in descending order afterward, it needs buffered storage. The same request to “make it descending” therefore implies different algorithms for arrays, linked lists and streams.

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. Define whether shared nodes and cycles are allowed. 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.

Before changing the code, state what makes the next value safe to emit:

Input: descending streams, or ascending arrays read from the end
Output: descending
Ownership: copy values, or explicitly permit node reuse
Invariant: every unseen value is no larger than its stream head

If the input contract cannot support that last sentence, change the access strategy or the algorithm. A different heap key cannot expose a value the input has kept hidden.