My rationale for asking "What if we just changed heapq back to working closer to the way it used to work?" is that it's a case where arbitrarily ordering unorderable tuples made sense, and reverting it to the old behaviour is reasonably safe:

- some Py3 heapq code that previously raised TypeError would start using an arbitrary ordering instead
- Py2 heapq code would get a *different* arbitrary ordering in Py3, but it would still get an arbitrary ordering

I don't feel especially strongly about that though, so if you prefer the approach of defining a new more explicit idiom to replace the old "make a tuple" one, I think a new wrapper type is a reasonable way to go, but using "Prioritize" as a name is probably too specific to the PriorityQueue use case.

As a more generic name, "KeyedItem" might work:

```
@functools.total_ordering
class KeyedItem:

    def __init__(self, key, item):
        self.key = key
        self.item = item

    def __eq__(self, other):
        return self.key == other.key

    def __lt__(self, other):
        return self.key < other.key
```

So applying an arbitrary key function would look like:

    decorated = [KeyedItem(key(v), v) for v in values]

And if it was a tuple subclass, it would also work with APIs like the dict constructor.