The main downside I see to that approach is that it would still require quite a few client code changes to restore compatibility for folks upgrading from 2.7, and even though six could add a "six.Prioritize" backport, it would still be difficult for automated tools to work out *where* such a wrapper would be appropriate.

So I'm wondering whether it might be worth defining a heapq.compareitem helper that special cases tuples, such that heapq switched to using a slightly modified definition of tuple comparisons:

    def compareitem(lhs, rhs):
        """<= variant that ensures all tuples are orderable"""
        is not isinstance(lhs, tuple) or not isinstance(rhs, tuple):
            return lhs <= rhs
        # Compare tuples up to first unequal pair
        for lhs_item, rhs_item in zip(lhs, rhs):
            if lhs_item != rhs_item:
                try:
                    return lhs_item < rhs_item
                except TypeError:
                    pass
                break
        # All item pairs equal, or unorderable pair found
        return len(lhs) <= len(rhs)

The key difference would be that if the heap-centric tuple comparison encounters a non-equal, unorderable pair of items, it would fall back to just comparing the tuple lengths (just as regular tuple comparison does when all item pairs are equal), rather than letting the TypeError propagate the way the default tuple comparison operator does.

The heap invariant would change slightly such that "storage.sort(key=heapq.compareitem)" would reliably preserve the heap invariant without raising an exception, while "storage.sort()" might instead fail with TypeError.