Как мне добавить списки из матрицы по определенному индексу при сохранении списка? - PullRequest
Новая
       11

Как мне добавить списки из матрицы по определенному индексу при сохранении списка?

0 голосов
/ 30 апреля 2018

Скажите, у меня есть список:

l1 = [[1, 3], [3, 2], [2, 1]]

Я хочу поместить каждый элемент в l1 в двоичную кучу, «память», но отсортирован в двоичной куче по each_item[-1].

Я пытался: heapq.heappush(_heap, item=itemgetter(-1)) и эквивалент с использованием анонимной функции, но я получаю:

TypeError: heappush() takes no keyword arguments

Ответы [ 4 ]

0 голосов
/ 30 апреля 2018

Мне нравится решение Юджина, но если много работать с этим специальным кортежем, можно определить пользовательский объект для достижения этого следующим образом: 

from heapq import heappush, heappop

class MyTupleHeapObj(object):
    def __init__(self,val): self.val = val
    def __lt__(self,other): return self.val[-1] < other.val[-1]
    def __eq__(self,other): return self.val == other.val
    def __str__(self): return str(self.val)

h = []
for item in [[1, 3], [3, 2], [2, 1]]:
    heappush(h, MyTupleHeapObj(item))

while h:
    print heappop(h)

Печатает следующее: 

[2, 1]
[3, 2]
[1, 3]
0 голосов
/ 30 апреля 2018

Вы можете хранить записи в куче как кортежи из 3 элементов, включая последний элемент, количество записей и фактический элемент. Таким образом, элементы будут отсортированы по последним значениям с количеством записей, обеспечивающим стабильность сортировки (то есть два элемента с одинаковыми последними элементами будут возвращены в порядке их добавления): 

>>> import heapq
>>> heap = []
>>> l1 = [[1, 3], [3, 2], [2, 1]]
>>> for count, item in enumerate(l1):
...     heapq.heappush(heap, (item[-1], count, item))
... 
>>> while heap:
...     print(heapq.heappop(heap)[-1])
... 
[2, 1]
[3, 2]
[1, 3]
0 голосов
/ 30 апреля 2018

Еще один вариант - определить свой собственный оператор меньше: 

class mylist(list):
     def __lt__(self,other): return self[-1] < other[-1]

Таким образом, вы можете иметь: 

myheap = []
for x in l1:
     heapq.heappush(myheap,mylist(x))

Это будет лучше масштабироваться при более сложных условиях и может быть сделано на лету.

Примечание heappush получает существующую кучу (так что список) и то, что вы хотите нажать - это была ваша ошибка (аргумент key не может использоваться с ним). Если вы не хотите тратить память (myheap), вы можете использовать 

l1 = [mylist(x) for x in l1] #Creates a new list, but allows clean up of the old one.
heapq.heapify(l1)

чтобы сделать l1 в вашу кучу.

0 голосов
/ 30 апреля 2018

Одним из вариантов является создание небольших оберток вокруг heapq функций для последовательного добавления / извлечения значения сортировки для / из элемента: 

def heappush(h, item, key=lambda x: x):
    heapq.heappush(h, (key(item), item))

def heappop(h):
    return heapq.heappop(h)[1]

def heapify(h, key=lambda x: x):
    for idx, item in enumerate(h):
        h[idx] = (key(item), item)
    heapq.heapify(h)

Тестирование с вашим образцом: 

l1 = [[1, 3], [3, 2], [2, 1]]
h = []
for item in l1:
    heappush(h, item, key=itemgetter(-1))

while h:
    print(heappop(h))

Печать: 

[2, 1]
[3, 2]
[1, 3]

Обратите внимание, что вы можете использовать h=l1; heapify(h, key=itemgetter(-1)), который должен быть быстрее, чем индивидуально heappush с каждым элементом.

...