built-in max heap API in Python

Question

Default heapq is min queue implementation and wondering if there is an option for max queue? Thanks.

I tried the solution using _heapify_max for max heap, but how to handle dynamically push/pop element? It seems _heapify_max could only be used during initialization time.

import heapq  def heapsort(iterable):     h = []     for value in iterable:         heapq.heappush(h, value)     return [heapq.heappop(h) for i in range(len(h))]  if __name__ == "__main__":      print heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) 

Edit, tried _heapify_max seems not working for dynamically push/pop elements. I tried both methods output the same, both output is, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].

def heapsort(iterable):     h = []     for value in iterable:         heapq.heappush(h, value)     return [heapq.heappop(h) for i in range(len(h))]  def heapsort2(iterable):     h = []     heapq._heapify_max(h)     for value in iterable:         heapq.heappush(h, value)     return [heapq.heappop(h) for i in range(len(h))]  if __name__ == "__main__":      print heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])     print heapsort2([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) 

Thanks in advance, Lin

Answer 1

In the past I have simply used sortedcontainers's SortedList for this, as:

> a = SortedList() > a.add(3) > a.add(2) > a.add(1) > a.pop() 3 

It's not a heap, but it's fast and works directly as required.

If you absolutely need it to be a heap, you could make a general negation class to hold your items.

class Neg():     def __init__(self, x):         self.x = x      def __cmp__(self, other):         return -cmp(self.x, other.x)  def maxheappush(heap, item):     heapq.heappush(heap, Neg(item))  def maxheappop(heap):     return heapq.heappop(heap).x 

But that will be using a little more memory.