Does python have a built in min-heap data structure?

Question

Does python have a built in min-heap data structure in 2.7.3?

I don't want to import code.

I want something like

myheap = minheap(key=lambda x: x[1])
myheap.add(obj)
o = myheap.pop()

Is this possible?

Answer 1

Like everybody says, heapq is it -- but, as nobody's mentioned yet, it doesn't support a key=! So you need to fall back to the good old DSU (decorate-sort-undecorate) idiom that key= uses internally wherever it's supported (alas not in heapq, except for the functions nlargest and nsmallest that don't really have much to do with the rest of the module).

So you can wrap heapq functionality, with the addition of a key, e.g in a class of your own:

import heapq

class MyHeap(object):
    def __init__(self, key, data=())
        self.key = key
        self.heap = [(self.key(d), d) for d in data]
        heapq.heapify(self.heap)

    def push(self, item):
        decorated = self.key(item), item
        heapq.heappush(self.heap, decorated)

    def pop(self):
        decorated = heapq.heappop(self.heap)
        return decorated[1]

    def pushpop(self, item):
        decorated = self.key(item), item
        dd = heapq.heappushpop(self.heap, decorated)
        return dd[1]

    def replace(self, item):
        decorated = self.key(item), item
        dd = heapq.heapreplace(self.heap, decorated)
        return dd[1]

    def __len__(self):
        return len(self.heap)

See https://docs.python.org/2/library/heapq.html for the distinction between pushpop and replace (and the other auxiliary functions supplied by standard library module heapq).

Answer 2

Python comes with heapq, which you don't have to download, but you still have to import.

Python has very little in the way of data structures you can use without using the import statement altogether. Do you really want your language to have its entire standard library loaded in memory and namespace for every project?