3

I'm trying to implement a min heap on a list of tuple. For example:

A=[('a',2),('b',1)]

how can I heapify A based on the second element of these tuple, so that A will be heapified to [('b',1),('a',2)] ? (I must maintain a min heap.)

user2906838
  • 1,178
  • 9
  • 20
MegaAndyZ
  • 51
  • 1
  • 3
  • 1
    What did you try? Please post your attempt. – DYZ Aug 26 '18 at 04:08
  • 1
    If you are specifying an exact ordering of all the items, then you are *not dealing with a heap*. In an actual heap, only the root item has a fixed location. – jasonharper Aug 26 '18 at 04:44
  • well, that is just an example. Just wanna maintain a min heap based on the second element of tuple on such a data structure. – MegaAndyZ Aug 26 '18 at 15:00
  • 1
    You'll use Python's heapq, and follow the advice given in the answer to https://stackoverflow.com/questions/8875706/heapq-with-custom-compare-predicate. Basically, create tuples like `(2, ('a', 2))` and `(1, ('b', 1))`. – Jim Mischel Aug 27 '18 at 12:51

2 Answers2

5

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)
pjs
  • 18,696
  • 4
  • 27
  • 56
  • someone trying for max heap can try this - heap_elts = [(item[1]*-1, item) for item in list] – minato Sep 06 '21 at 14:44
0
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')]
Gary Bao 鲍昱彤
  • 2,608
  • 20
  • 31