Search code examples
pythonpriority-queue

Heapify list based on 2nd element of pair in python

Inbuilt python function

heaps.heapify(x)

will heapify list x. Now if the elements of the list are in pairs, this function will heapify the list based on 1st element of each pair (a,b), i.e a. What if I want to heapify the list based on 2nd element of pair, i.e, b. Is there any inbuilt way to heapify the list based on 2nd element of list?

x = [(1,2), (2,1), (3,4), (4,3), (5,6), (1,4), (4,2), (2,5)]

Now output of heapq.heapify(x) would be 

>>> [(1,2), (1,4), (2,1), (2,5), (3,4), (4,3), (4,2), (5,6)]

Above is the order in pairs will be popped out of list.How can I heapify list so that output of heapify function is something like this:-

>>> [(2,1), (1,2), (4,2), (4,3), (3,4), (1,4), (2,5), (5,6)]

I know that this can be obtained by writing elements in each pair in reverse order, but I want to know if there is some inbuilt way to do so in python.

Solution

  • You could append each element into the heap in whatever order you want. Heap recognizes them as (num1, num2) where num1 is used for ranking. Below is an option:

    hp = []
for e in x:
    hp.append((e[1], e[0]))

heapq.heapify(hp)
new = []
while hp:
    y = heapq.heappop(hp)
    new.append([y[1], y[0]])
print(new)

    The array new will have the order you want.