Je vérifiais cette solution à une question sur 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)]
et quand je lui donne un tableau de chaînes comme ["aa", "aaa", "a"] et 1 il renvoie correctement ["a"] . Ma question est la suivante: le tas a-t-il également trié lexographiquement les tuples en interne? Parce que selon moi, s'il n'y avait pas de tri, il aurait simplement renvoyé ["aa"] (l'ordre dans lequel le tas a été construit puisque les nombres des trois sont les mêmes). Ou ai-je mal compris heapq ?
4 Réponses :
Vous avez un tas de paires entiers / chaînes, et donc il est ordonné en fonction de la définition de < pour les tuples, qui prend en compte les deux éléments de chaque type.
Étant donné ["aa", "aaa", "a"] , count.items() est une séquence de tuples [('aa', 1), ('aaa', 1), ('a', 1)] . Vous construisez ensuite un tas en utilisant la liste des tuples
[(-1, 'aa'), (-1, 'aaa'), (-1, 'a')]
Puisque le premier élément de chaque tuple est le même, les comparaisons sont déterminées uniquement par le deuxième élément, string.
Les tas sont des ordres partiels. Ils ne sont pas triés. Vous pouvez, cependant, en créer des tris en stockant les valeurs dans un tas et en les extrayant une à la fois. Ces tris ne sont pas stables, car les tas n'essaient pas de conserver l'ordre des valeurs «égales».
Voici un autre type de tas Python qui pourrait vous intéresser: https://pypi.org/project/fibonacci-heap-mod/
Bien qu'il soit intéressant de noter que les tas obéissent à la propriété de tas , ce qu'une liste triée satisfait. Un tas n'a pas besoin d'être trié, mais cela peut l' être.
heapq compare simplement les valeurs de la file d'attente en utilisant l'opérateur "inférieur à" [1] quel que soit le type de valeur. C'est le type de valeur qui définit ce que la comparaison retournera. Donc, ce qui fait la différence ici, c'est le tuple lui-même. A partir de la documentation :
La comparaison [des objets de séquence] utilise un ordre lexicographique: d'abord les deux premiers éléments sont comparés, et s'ils diffèrent, cela détermine le résultat de la comparaison; s'ils sont égaux, les deux éléments suivants sont comparés, et ainsi de suite, jusqu'à ce que l'une ou l'autre des séquences soit épuisée.
Vérification de quelques exemples:
cmp = PyObject_RichCompareBool(newitem, parent, Py_LT);
Vous avez donc raison, les valeurs sont ordonnées lexicographiquement et la deuxième valeur du tuple est pertinente. Cependant, heapq n'a rien à faire ici pour obtenir ce résultat, la simple comparaison de tuple fait cela.
[1] On peut le vérifier dans le code. Voici l' une des lignes où la comparaison est faite par heapq (en C):
>>> (0, 'a') < (1, 'aa') True >>> (1, 'a') < (1, 'aa') True >>> (1, 'aa') < (1, 'a') False >>> (2, 'a') < (1, 'aa') False
Ce PyObject_RichCompareBool() est, selon la documentation :
l'équivalent de l'expression Python o1 op o2, où op est l'opérateur correspondant à opid .
Plus d'informations sur les comparaisons de tuple ici .
Très bonne réponse. Il est dommage que les documents de l'API eux-mêmes n'éclairent pas beaucoup sur la comparaison des tuples dans un heapq.
L'attente de la question leetcode est de résoudre le problème en O (nlogk). Nous devons donc conserver uniquement les éléments 'k' dans le tas à tout moment, ce qui signifie que nous devons utiliser "minHeap" (freq, word) et non (-freq, word).
Nous voulons que «minHeap» garde la valeur «fréquence minimale» et «max lexicographique» en haut du tas. C'est délicat, car par défaut, il conserverait «fréquence minimale» et «lex min».
La seule solution est de créer un objet pouvant avoir 'freq' et 'word' et de remplacer la méthode ' lt ' pour ce faire
def __lt__(self, other):
if self.c == other.c:
return self.w > other.w
return self.c < other.c
Trié, non. Commandé , oui. (Bien que l'ordre choisi puisse être par hasard un ordre trié.)