According to the example from the documentation, you can use tuples, and it will sort by the first element of the tuple:

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

So if you don't want to (or can't?) do a __cmp__ method, you can manually extract your sorting key at push time.

Note that if the first elements in a pair of tuples are equal, further elements will be compared. If this is not what you want, you need to ensure that each first element is unique.

heapq is a binary heap, with O(log n) push and O(log n) pop. See the heapq source code.

The algorithm you show takes O(n log n) to push all the items onto the heap, and then O((n-k) log n) to find the kth largest element. So the complexity would be O(n log n). It also requires O(n) extra space.

You can do this in O(n log k), using O(k) extra space by modifying the algorithm slightly. I'm not a Python programmer, so you'll have to translate the pseudocode:

# create a new min-heap
# push the first k nums onto the heap
for the rest of the nums:
    if num > heap.peek()
        heap.pop()
        heap.push(num)

# at this point, the k largest items are on the heap.
# The kth largest is the root:

return heap.pop()

The key here is that the heap contains just the largest items seen so far. If an item is smaller than the kth largest seen so far, it's never put onto the heap. The worst case is O(n log k).

Actually, heapq has a heapreplace method, so you could replace this:

    if num > heap.peek()
        heap.pop()
        heap.push(num)

with

    if num > heap.peek()
        heap.replace(num)

Also, an alternative to pushing the first k items is to create a list of the first k items and call heapify. A more optimized (but still O(n log k)) algorithm is:

# create array of first `k` items
heap = heapify(array)
for remaining nums
    if (num > heap.peek())
        heap.replace(num)
return heap.pop()

You could also call heapify on the entire array, then pop the first n-k items, and then take the top:

heapify(nums)
for i = 0 to n-k
    heapq.heappop(nums)
return heapq.heappop(nums)

That's simpler. Not sure if it's faster than my previous suggestion, but it modifies the original array. The complexity is O(n) to build the heap, then O((n-k) log n) for the pops. So it's be O((n-k) log n). Worst case O(n log n).

The easiest way is to invert the value of the keys and use heapq. For example, turn 1000.0 into -1000.0 and 5.0 into -5.0.

You can store entries in the heap as 3-element tuples including the last element, an entry count, and the actual item. This way the items will be sorted by their last values with the entry count ensuring sort stability (i.e. two items with equal last elements are returned in the order they were added):

>>> import heapq
>>> heap = []
>>> l1 = [[1, 3], [3, 2], [2, 1]]
>>> for count, item in enumerate(l1):
...     heapq.heappush(heap, (item[-1], count, item))
... 
>>> while heap:
...     print(heapq.heappop(heap)[-1])
... 
[2, 1]
[3, 2]
[1, 3]