Сравнивает ли heapq.heappu sh () строку int и строку, для которой не было указано? - PullRequest
Новая
       51

Сравнивает ли heapq.heappu sh () строку int и строку, для которой не было указано?

1 голос
/ 19 февраля 2020

Я проверял это решение на вопрос leetcode.com 

def topKFrequent(self, words, k):
        count = collections.Counter(words)
        heap = [(-freq, word) for word, freq in count.items()]
        heapq.heapify(heap)
        return [heapq.heappop(heap)[1] for _ in xrange(k)]

, и когда я предоставляю ему массив строк, таких как ["aa", "aaa", "a"] и 1, это правильно возвращает ["a"]. У меня такой вопрос: лексографически ли лексографически сортирует кортежи внутри? Потому что, по моему мнению, если бы не было сортировки, она просто вернула бы ["aa"] (порядок, в котором была построена куча, так как числа всех трех одинаковы). Или я неправильно понял heapq?

Ответы [ 3 ]

3 голосов
/ 19 февраля 2020

У вас есть куча пар целое число / строка, и поэтому она упорядочена на основе определения < для кортежей, которое учитывает оба элемента каждого типа.

Учитывая ["aa", "aaa", "a"], count.items() - это последовательность кортежей [('aa', 1), ('aaa', 1), ('a', 1)]. Затем вы создаете кучу, используя список кортежей 

[(-1, 'aa'), (-1, 'aaa'), (-1, 'a')]

Поскольку первый элемент каждого кортежа одинаков, сравнения определяются только вторым, строковым, элементом.

1 голос
/ 19 февраля 2020

heapq просто сравнивает значения из очереди, используя оператор «меньше чем» [1] независимо от типа значения. Это тип значения, которое определяет, что будет возвращать сравнение. Таким образом, дерьмо имеет значение здесь сам кортеж. Начиная с документации :

Для сравнения [объектов последовательности] используется лексикографическое упорядочение: сначала сравниваются первые два элемента, и если они отличаются, определяет результат сравнения; если они равны, сравниваются следующие два элемента и т. д., пока не будет исчерпана любая последовательность.

Проверка некоторых примеров: 

>>> (0, 'a') < (1, 'aa')
True
>>> (1, 'a') < (1, 'aa')
True
>>> (1, 'aa') < (1, 'a')
False
>>> (2, 'a') < (1, 'aa')
False

Итак, вы правы, значения упорядочены лексикографически, и второе значение кортежа является релевантным. Однако heapq здесь не нужно ничего делать, чтобы получить этот результат, это делает простое сравнение кортежей.

[1] Это можно проверить в коде. Здесь - это одна из строк, где сравнение выполняется на heapq (в C): 

cmp = PyObject_RichCompareBool(newitem, parent, Py_LT);

Это PyObject_RichCompareBool(), согласно документации :

эквивалент Python выражения o1 op o2, где op - оператор, соответствующий opid .

0 голосов
/ 19 февраля 2020

Кучи - это частичные заказы. Они не отсортированы. Однако вы можете создавать сортировки из них, сохраняя значения в куче и извлекая их по одному за раз. Эти виды не являются стабильными, потому что кучи не пытаются сохранить порядок «равных» значений.

Вот еще один вид Python кучи, который может вас заинтересовать: https://pypi.org/project/fibonacci-heap-mod/

...