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.

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).

As others have observed, if the heap accepts a comparator, then it's not too hard to get one behavior or the other. A quick perusal of Google Code, however, suggests that min-heap is by far more prevalent in actual code, because of two applications that come up again and again.

• Dijkstra/A*/many other shortest path algorithms (because partial paths get longer).

• Event simulation (because time goes forward).

Also, I would argue that because the default sort returns items small to large, so should the default heap.

As per @JimMischel's comment, place your tuples in a tuple with the priority as the first element. Then use heapq:

import heapq

list = [('a', 2), ('b', 1), ('c', 0), ('d', 1)]
heap_elts = [(item[1], item) for item in list]
heapq.heapify(heap_elts)  # you specifically asked about heapify, here it is!
while len(heap_elts) > 0:
    print(heapq.heappop(heap_elts)[1])    # element 1 is the original tuple

produces:

('c', 0)
('b', 1)
('d', 1)
('a', 2)

Thanks for sharing your code!

I won't cover all your questions but I will try my best.

(warning, long post incoming)

Is my implementation correct? (The tests say so)

As far as I tried to break it I'd say yes it's correct. But see below for more thorough testing methods.

Can it be sped up?

Spoiler alert: yes

First thing I did was to profile change slightly your test file (I called it test_heap.py) to seed the random list generation. I also changed the random.sample call to be more flexible with the sample_size parameter.

It went from

random_numbers = random.sample(range(100), sample_size)

to

random.seed(7777)
random_numbers = random.sample(range(sample_size * 3), sample_size)

So the population from random.sample is always greater than my sample_size. Maybe there is a better way?

I also set the sample size to be 50000 to have a decent size for the next step.

Next step was profiling the code with python -m cProfile -s cumtime test_heap.py . If you are not familiar with the profiler see the doc. I launch the command a few times to get a grasp of the variations in timing, that gives me a baseline for optimization. The original value was:

  7990978 function calls (6561934 primitive calls) in 3.235 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      5/1    0.000    0.000    3.235    3.235 {built-in method builtins.exec}
        1    0.002    0.002    3.235    3.235 test_heap.py:1(<module>)
        1    0.051    0.051    3.233    3.233 test_heap.py:43(automaticTest)
   100009    0.086    0.000    2.759    0.000 heap.py:15(pop)
1400712/100011    1.688    0.000    2.673    0.000 heap.py:70(__siftdown)
  1400712    0.386    0.000    0.386    0.000 heap.py:104(__get_left_child)
  1400712    0.363    0.000    0.363    0.000 heap.py:110(__get_right_child)
   100008    0.064    0.000    0.341    0.000 heap.py:6(push)
228297/100008    0.180    0.000    0.270    0.000 heap.py:85(__siftup)
  1430126    0.135    0.000    0.135    0.000 heap.py:127(comparer)
  1429684    0.128    0.000    0.128    0.000 heap.py:131(comparer)
   228297    0.064    0.000    0.064    0.000 heap.py:98(__get_parent)
        1    0.026    0.026    0.062    0.062 random.py:286(sample)

Now we have a target to beat and a few information on what takes time. I did not paste the entire list of function calls, it's pretty long but you get the idea.

A lot of time is spent in _siftdown and a lot less on _siftup, and a few functions are called many times so let's see if we can fix that.

(I should have started by _siftdown which was the big fish here but for some reason, I started by _siftup, forgive me)

Speeding up _siftup

Before:

def __siftup(self, index):
    current_value = self.__array[index]
    parent_index, parent_value = self.__get_parent(index)
    if index > 0 and self.comparer(current_value, parent_value):
        self.__array[parent_index], self.__array[index] =\
            current_value, parent_value
        self.__siftup(parent_index)
    return

After:

def __siftup(self, index):
    current_value = self.__array[index]
    parent_index = (index - 1) >> 1
    if index > 0:
        parent_value = self.__array[parent_index]
        if self.comparer(current_value, parent_value):
            self.__array[parent_index], self.__array[index] =\
                current_value, parent_value
            self.__siftup(parent_index)
    return

I changed the way to calculate parent_index because I looked at the heapq module source and they use it. (see here) but I couldn't see the difference in timing from this change alone.

Then I removed the call to _get_parent and made the appropriate change (kind of inlining it because function call are not cheap in Python) and the new time is

7762306 function calls (6333638 primitive calls) in 3.147 seconds

Function calls went down obviously but time only dropped around 70-80 millisecond. Not a great victory (a bit less than a 3% speedup). And readability was not improved so up to you if it is worth it.

Speeding up _siftdown

The first change was to improve readability.

Original version:

def __siftdown(self, index):
    current_value = self.__array[index]
    left_child_index, left_child_value = self.__get_left_child(index)
    right_child_index, right_child_value = self.__get_right_child(index)
    # the following works because if the right_child_index is not None, then the left_child
    # is also not None => property of a complete binary tree, else left will be returned.
    best_child_index, best_child_value = (right_child_index, right_child_value) if right_child_index\
    is not None and self.comparer(right_child_value, left_child_value) else (left_child_index, left_child_value)
    if best_child_index is not None and self.comparer(best_child_value, current_value):
        self.__array[index], self.__array[best_child_index] =\
            best_child_value, current_value
        self.__siftdown(best_child_index)
    return

V2:

def __siftdown(self, index): #v2
    current_value = self.__array[index]
    left_child_index, left_child_value = self.__get_left_child(index)
    right_child_index, right_child_value = self.__get_right_child(index)
    # the following works because if the right_child_index is not None, then the left_child
    # is also not None => property of a complete binary tree, else left will be returned.
    best_child_index, best_child_value = (left_child_index, left_child_value)
    if right_child_index is not None and self.comparer(right_child_value, left_child_value):
        best_child_index, best_child_value = (right_child_index, right_child_value)
    if best_child_index is not None and self.comparer(best_child_value, current_value):
        self.__array[index], self.__array[best_child_index] =\
            best_child_value, current_value
        self.__siftdown(best_child_index)
    return

I transformed the ternary assignment

best_child_index, best_child_value = (right_child_index, right_child_value) if right_child_index\
        is not None and self.comparer(right_child_value, left_child_value) else (left_child_index, left_child_value)

into

best_child_index, best_child_value = (left_child_index, left_child_value)
if right_child_index is not None and self.comparer(right_child_value, left_child_value):
    best_child_index, best_child_value = (right_child_index, right_child_value)

I find it a lot more readable but it's probably a matter of taste. And to my surprise, when I profiled the code again, the result was:

7762306 function calls (6333638 primitive calls) in 3.079 seconds

(I ran it 10times and I always had gained around 80-100 milliseconds). I don't really understand why, if anybody could explain to me?

V3:

def __siftdown(self, index): #v3
    current_value = self.__array[index]
    
    left_child_index = 2 * index + 1
    if left_child_index > self.__last_index:
        left_child_index, left_child_value = None, None
    else:
        left_child_value = self.__array[left_child_index]
    
    right_child_index = 2 * index + 2
    if right_child_index > self.__last_index:
         right_child_index, right_child_value = None, None
    else:
        right_child_value = self.__array[right_child_index]
    # the following works because if the right_child_index is not None, then the left_child
    # is also not None => property of a complete binary tree, else left will be returned.
    best_child_index, best_child_value = (left_child_index, left_child_value)
    if right_child_index is not None and self.comparer(right_child_value, left_child_value):
        best_child_index, best_child_value = (right_child_index, right_child_value)
    if best_child_index is not None and self.comparer(best_child_value, current_value):
        self.__array[index], self.__array[best_child_index] =\
            best_child_value, current_value
        self.__siftdown(best_child_index)
    return

Like in _siftup I inlined 2 calls from helper function _get_left_child and _get_right_child and that payed off!

4960546 function calls (3531878 primitive calls) in 2.206 seconds

That's a 30% speedup from the baseline.

(What follow is a further optimization that I try to explain but I lost the code I wrote for it, I'll try to right down again later. It might gives you an idea of the gain)

Then using the heapq trick of specializing comparison for max and min (using a _siftdown_max and _siftup_max version replacing comparer by > and doing the same for min) gives us to:

2243576 function calls (809253 primitive calls) in 1.780 seconds

I did not get further in optimizations but the _siftdown is still a big fish so maybe there is room for more optimizations? And pop and push maybe could be reworked a bit but I don't know how.

Comparing my code to the one in the heapq module, it seems that they do not provide a heapq class, but just provide a set of operations that work on lists? Is this better?

I'd like to know as well!

Many implementations I saw iterate over the elements using a while loop in the siftdown method to see if it reaches the end. I instead call siftdown again on the chosen child. Is this approach better or worse?

Seeing as function call are expensive, looping instead of recursing might be faster. But I find it better expressed as a recursion.

Is my code clean and readable?

For the most part yes! Nice code, you got docstrings for your public methods, you respect PEP8 it's all good. Maybe you could add documentation for the private method as well? Especially for hard stuff like _siftdown and _siftup.

Just a few things:

• the ternary I changed in _siftdown I consider personally really hard to read.

• comparer seems like a French name, why not compare? Either I missed something or you mixed language and you shouldn't.

Do my test suffice (for say an interview)?

I'd say no. Use a module to do unit testing. I personally like pytest.

You prefix the name of your testing file by test_ and then your tests methods are prefixed/suffixed by test_/_test. Then you just run pytest on the command line and it discovers tests automatically, run them and gives you a report. I highly recommend you try it.

Another great tool you could have used is hypothesis which does property-based testing. It works well with pytest.

An example for your case:

from hypothesis import given, assume
import hypothesis.strategies as st

@given(st.lists(st.integers()))
def test_minheap(l):
    h = MinHeap.createHeap(l)
    s = sorted(l)
    for i in range(len(s)):
        assert(h.pop() == s[i])
        
@given(st.lists(st.integers()))
def test_maxheap(l):
    h = MaxHeap.createHeap(l)
    s = sorted(l, reverse=True)
    for i in range(len(s)):
        assert(h.pop() == s[i])

It pretty much gives the same kind of testing you did in your automatic_test but gets a bunch of cool feature added, and is shorter to write.

Raymond Hettinger did a really cool talk about tools to use when testing on a short time-budget, he mention both pytest and hypothesis, go check it out :)

Is the usage of subclasses MinHeap and MaxHeap & their comparer method that distincts them, a good approach to provide both type of heaps?

I believe it is! But speed wise, you should instead redeclare siftdown and siftup in the subclasses and replace instance of compare(a,b) by a < b or a > b in the code.

End note

Last thing is a remark, on wikipedia, the article say:

sift-up: move a node up in the tree, as long as needed; used to restore heap condition after insertion. Called "sift" because node moves up the tree until it reaches the correct level, as in a sieve.

sift-down: move a node down in the tree, similar to sift-up; used to restore heap condition after deletion or replacement.

And I think you used it in this context but on the heapq module implementation it seems to have the name backward?

They use siftup in pop and siftdown in push while wikipedia tells us to do the inverse. Somebody can explain please?

(I asked this question on StackOverflow, hopefully I'll get a response)