Die erste Implementation verwendet ein einfaches, unsortiertes Array. Wenn max oder delmax aufgerufen werden, wird das groesste Element gesucht und mit dem letzten vertauscht.
class MaxPQUnorderedArray:
def __init__(self):
self._data = []
def insert(self, k):
self._data.append(k)
def max(self):
self._largestToEnd()
return self._data[-1]
def delMax(self):
self._largestToEnd()
return self._data.pop()
def _largestToEnd(self):
if len(self._data) == 0:
return
maxElem = self._data[0]
maxIndex = 0
for i, d in enumerate(self._data):
if (maxElem < d):
maxElem = self._data[i]
maxIndex = i
self._data[maxIndex], self._data[-1] = self._data[-1], self._data[maxIndex]
def isEmpty(self):
return len(self._data) == 0
def size(self):
return len(self._data)
Bei der zweiten einfachen Implementation, wird das neue Element jeweils an die richtige Position im Array eingefuegt. Die Insert methode wird dadurch aufwaendiger, dafuer sind die Methoden max und delmax sehr einfach und effizient.
class MaxPQOrderedArray:
def __init__(self):
self._data = []
def insert(self, k):
# Suche im sortierten Array data die Position vom neuen Element
idx = 0
while (idx < len(self._data) and self._data[idx] < k):
idx += 1
self._data.insert(idx, k)
def max(self):
if self.isEmpty():
return None
else:
return self._data[-1]
def delMax(self):
return self._data.pop()
def isEmpty(self):
return len(self._data) == 0
def size(self):
return len(self._data)
import timeit
import random
def insertNElements(pq, N):
for i in range(0, N):
pq.insert(i)
def removeLargestNElements(pq, N):
for i in range(0, N):
pq.delMax()
orderedPQ = MaxPQOrderedArray()
unorderedPQ = MaxPQUnorderedArray()
print("insert ordered ", timeit.timeit(lambda: insertNElements(orderedPQ, 10000), number = 1))
print("insert unordered", timeit.timeit(lambda: insertNElements(unorderedPQ, 10000), number = 1))
print("removeLargest ordered", timeit.timeit(lambda: removeLargestNElements(orderedPQ, 10000), number = 1))
print("removeLargest unordered", timeit.timeit(lambda: removeLargestNElements(unorderedPQ, 10000), number = 1))
insert ordered 14.847693462278073 insert unordered 0.0025770063864882786 removeLargest ordered 0.0028787587672383097 removeLargest unordered 7.773102326490331
Eine typische Beispielanwendung ist, dass man aus einem sehr grossen Datenstrom die groessten Elemente extrahieren moechte. Um das Beispiel hier minimal zu halten, und trotzdem die Moeglichkeit zu haben grosse Streams zu generiern, ziehen wir Zufallszahlen von einer Normalverteilung.
Die folgende Funktion generiert einen Stream von $n$ normalverteilen Zufallszahlen
import random
def numberGen(n):
num = 0
while num < n:
yield random.normalvariate(0, 1)
num += 1
Unser Beispielclient fuegt $N$ zufaellig Zahlen in eine Priorityqueue ein. Wenn die gewuenschte Anzahl von groessten Zahlen $M$ erreicht ist wird immer die jeweils kleinste entfernt, um wieder Platz fuer eine neue groesste Zahl zu schaffen. Am ende sind dann die $M$ groessten Zahlen in der Queue, und wir muessen diese nur noch entfernen.
Achtung: Dies wuerde man am besten mit einer Minimumsorientierten Priorityqueue loesen. In der Praxis hat man aber selten beide Varianten zur Verfuegung. Wir helfen uns damit, dass wir einfach das negative der Zufallszahl hinzufuegen, und dies beim auslesen nochmals negieren.
def printSmallestNumber(pq, M, N):
for number in numberGen(N):
pq.insert(-1.0 * number)
if (pq.size() > M):
pq.delMax();
while not pq.isEmpty():
print(-1.0 * pq.delMax())
printSmallestNumber(MaxPQUnorderedArray(), 10, 10000000)
4.720127899688404 4.736890376900317 4.770395183027388 4.789451908203996 4.832946315426965 4.888526854766741 4.940155531283058 4.984392568216207 5.049331886942966 5.068454372783877
Uebung: Schreiben Sie einen Client, der aus einem gegebenen Text mittels demselben Verfahren die laengsten $M$ Woerter bestimmt.