2

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.

Ruchit Vithani
  • 331
  • 4
  • 12
  • output is order in which each element will be popped out of heap. I don't know what will be output after heaps.heapify(x) on printing x, but I am talking about order in which elements will be popped out of list. – Ruchit Vithani Sep 14 '18 at 08:20
  • What is `heaps`? Did you mean `heapq`? – tobias_k Sep 14 '18 at 08:41
  • 2
    AFAIK `heapq` does not support key functions. Workarounds would be to wrap the tuple inside another tuple, repeating the key element (i.e. `(4,2)` -> `(2, (4,2))`). You could also define helper functions for transforming the tuples when pushing and popping items to and from the heap. – tobias_k Sep 14 '18 at 08:43
  • @tobias_k yes, that is typo. I meant heapq. – Ruchit Vithani Sep 14 '18 at 09:11
  • See https://stackoverflow.com/q/8875706/56778. You'll have to make a tuple with the first item being the second item from each of your tuples. (Yeah, that sounds confusing.) Basically, create this `[(2,(1,2)),(1, (2,1)), (4,(3,4)) ...]`. – Jim Mischel Sep 18 '18 at 17:22

1 Answers1

1

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.

XWZ
  • 743
  • 5
  • 7