Solution: Wrap data with the new comparison
Since the builtin functions don't directly support cmp functions, we need to build new variants of heapify and heappop:
from heapq import heapify, heappop
from functools import cmp_to_key
def new_heapify(data, cmp):
s = list(map(cmp_to_key(cmp), data))
heapify(s)
return s
def new_heappop(data):
return heappop(data).obj
Those are used just like your example:
>>> l = [ ['a', 3], ['b', 1] ]
>>> def foo(x, y):
... return x[1]-y[1]
...
>>> heap = new_heapify(l, cmp=foo)
>>> new_heappop(heap)
['b', 1]
Solution: Store Augmented Tuples
A more traditional solution is to store (priority, task) tuples on the heap:
pq = [ ]
heappush(pq, (10, task1))
heappush(pq, (5, task2))
heappush(pq, (15, task3))
priority, task = heappop(pq)
This works fine as long as no two tasks have the same priority; otherwise, the tasks themselves are compared (which might not work at all in Python 3).
The regular docs give guidance on how to implement priority queues using heapq:
http://docs.python.org/library/heapq.html#priority-queue-implementation-notes
Answer from Raymond Hettinger on Stack OverflowVideos
Solution: Wrap data with the new comparison
Since the builtin functions don't directly support cmp functions, we need to build new variants of heapify and heappop:
from heapq import heapify, heappop
from functools import cmp_to_key
def new_heapify(data, cmp):
s = list(map(cmp_to_key(cmp), data))
heapify(s)
return s
def new_heappop(data):
return heappop(data).obj
Those are used just like your example:
>>> l = [ ['a', 3], ['b', 1] ]
>>> def foo(x, y):
... return x[1]-y[1]
...
>>> heap = new_heapify(l, cmp=foo)
>>> new_heappop(heap)
['b', 1]
Solution: Store Augmented Tuples
A more traditional solution is to store (priority, task) tuples on the heap:
pq = [ ]
heappush(pq, (10, task1))
heappush(pq, (5, task2))
heappush(pq, (15, task3))
priority, task = heappop(pq)
This works fine as long as no two tasks have the same priority; otherwise, the tasks themselves are compared (which might not work at all in Python 3).
The regular docs give guidance on how to implement priority queues using heapq:
http://docs.python.org/library/heapq.html#priority-queue-implementation-notes
Just write an appropriate __lt__ method for the objects in the list so they sort correctly:
class FirstList(list):
def __lt__(self, other):
return self[0] < other[0]
lst = [ ['a', 3], ['b', 1] ]
lst = [FirstList(item) for item in lst]
Only __lt__ is needed by Python for sorting, though it's a good idea to define all of the comparisons or use functools.total_ordering.
You can see that it is working by using two items with the same first value and different second values. The two objects will swap places when you heapify no matter what the second values are because lst[0] < lst[1] will always be False. If you need the heapify to be stable, you need a more complex comparison.
Does heapify take an unordered array and convert it into a heap in O(n) time ? I think this is specific to Python and there is some fancy math on why.
But in other languages like JavaScript for example, is n log n, this makes sense to me since you are adding n elements and each takes log n time. And how you have a sorted heap.
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]