Menu
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
593
A Max-Heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node.
A heap in Python is by default Min-heap, and is used using the heapq module's heapify , heappop , and heappush functions. To create and use a max-heap using library functions, we can multiply each element with -1 and then use the heap library function, and hence it will act as a max-heap.
The heapq module of python implements the heap queue algorithm. It uses the min heap where the key of the parent is less than or equal to those of its children.
The Python heapq module implements heap operations on lists. Unlike many other modules, it does not define a custom class. The Python heapq module has functions that work on lists directly. Usually, as in the email example above, elements will be inserted into a heap one by one, starting with an empty heap.
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.
147
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
