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.
Answer from Jander on Stack OverflowAccording 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 sorts objects the same way list.sort does, so just define a method __cmp__() within your class definition, which will compare itself to another instance of the same class:
def __cmp__(self, other):
return cmp(self.intAttribute, other.intAttribute)
Works in Python 2.x.
In 3.x use:
def __lt__(self, other):
return self.intAttribute < other.intAttribute
Videos
If I have A=[(1,30),(2,10),(3,15),(4,89),(5,60)] How do I use the heapify function on the 1st index of each tuple? In order to get A=[(2,10),(3,15),(1,30),(5,60),(4,89)]
To make a heap based on the first (0 index) element:
import heapq
heapq.heapify(A)
If you want to make the heap based on a different element, you'll have to make a wrapper class and define the __cmp__() method.
u/jpritcha3-14 has the right answer for what you asked. However, are you sure you want heapify and not sorted? Heapify wouldn't give you A=[(2,10),(3,15),(1,30),(5,60),(4,89)], it would give you [(2, 10), (1, 30), (3, 15), (4, 89), (5, 60)]. For what you want, you can run
sorted(A, key=lambda x: x[1])If you do really want heapify for this very specific purpose, and don't feel like making a wrapper class, one slightly silly workaround would be
A = [(j, i) for i, j in A]
heapify(A)
A = [(j, i) for i, j in A]or even wrap it in a function
def heap_index_1(arr):
arr = [(j, i) for i, j in arr]
heapify(arr)
arr = [(j, i) for i, j in arr]I've saw that when setting tuple item as heap element, it would get the first value while popping minimum values from heap.
heap = [(1, 10), (2, 99)]
For the above heap, it's obvious that it would pop the element (1, 10) first, since first elemnt of tuple 1 < 2
However, for those tuple elements where first element is same
heap = [(1, 10), (1, 99)]
I've tested some cases, heap would drop the element (1, 10) first, looks like it compares the second element when first element is same for multiples.
Is that the correct logic that heap would compare following values while first element is the same for tuples?
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)
import heapq
A=[('a',2),('b',1), ('d', 0), ('c', 2), ('a', 2)]
h = []
for el in A:
heapq.heappush(h, (el[1], el[0]))
print(h)
result:
[(0, 'd'), (2, 'a'), (1, 'b'), (2, 'c'), (2, 'a')]
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 use
import heapq
listForTree = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
heapq.heapify(listForTree) # for a min heap
heapq._heapify_max(listForTree) # for a maxheap!!
If you then want to pop elements, use:
heapq.heappop(minheap) # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap
The documentation says,
Our pop method returns the smallest item, not the largest (called a “min heap” in textbooks; a “max heap” is more common in texts because of its suitability for in-place sorting).
So you cannot get a max heap directly. However, one way to get it indirectly is to push the negative of the item on the heap, then take the negative again just after you pop the item. So instead of heappush(h, (200, 1)) you execute heappush(h, (-200, -1)). And to pop and print the max item, execute
Copynegmaxitem = heappop(h)
maxitem = (-negmaxitem[0], -negmaxitem[1])
print(maxitem)
There are other ways to get the same effect, depending on what exactly you are storing in the heap.
Note that trying h[-1] in a min-heap does not work to find the max item--the heap definition does not guarantee the max item will end up at the end of the list. nlargest should work but has time complexity of O(log(n)) to just examine the largest item in a min-heap, which defeats the purpose of the heap. My way has time complexity O(1) in the negative-heap to examine the largest item.
Why not use a PriorityQueue object? You can store (priority,key) tuples. One easy solution to make a max-heap would be to make priority be the opposite of key:
Copyfrom Queue import PriorityQueue
pq = PriorityQueue()
for i in range(10): # add 0-9 with priority = -key
pq.put((-i,i))
print(pq.get()[1]) # 9