Max Heap in Python abrufen

1. Max Heap mit Zahlen in Python erhalten
2. Max Heap mit Tupeln in Python ermitteln
3. Verweise

Der Heap ist die Datenstruktur der Wahl zum Implementieren einer Prioritätswarteschlange. Im Gegensatz zu einem binären Suchbaum ist ein Heap nicht vollständig geordnet; Es gibt keine eindeutige Reihenfolge zwischen Geschwistern oder Cousins.

In Python implementiert das heapq-Modul den Heap-Queue-Algorithmus. heapq bietet jedoch nur die Min Heap-Implementierung, bei der der Wert eines übergeordneten Knotens kleiner oder gleich einem der Werte seiner untergeordneten Knoten ist.

Die Hauptfunktion heappop() gibt das kleinste Element des Heaps zurück.

In diesem Artikel wird die Implementierung des Max-Heap-Verhaltens in Python erörtert, indem heapq mit benutzerdefiniertem Code kombiniert wird.

Max Heap mit Zahlen in Python erhalten

Die häufigste Strategie im Umgang mit Zahlen ist die Multiplikation der Elemente der Liste mit -1. Die heapq-Funktionen können sich um den Heap kümmern.

Nachdem wir den kleinsten Wert ausgegeben haben, müssen wir die Ausgabe erneut mit -1 multiplizieren, um den maximalen Wert zu erhalten.

Beispielcode:

# import the heapq module.
import heapq

# Max Heap With Numbers

# Create a list.
x = [5, 4, 3, 6, 8, 7, 2, 1]
# Print the list.
print(x)

# Multiply elements by -1.
x_inv = [-1 * i for i in x]
print(x_inv)

# Make the heap.
heapq.heapify(x_inv)

# Pop the maximum value.
# RUN ONE LINE AT A TIME.
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)

Ausgabe:

print(x)
[5, 4, 3, 6, 8, 7, 2, 1]

print(x_inv)
[-5, -4, -3, -6, -8, -7, -2, -1]

-1 * heapq.heappop(x_inv)
Out[8]: 8

-1 * heapq.heappop(x_inv)
Out[9]: 7

-1 * heapq.heappop(x_inv)
Out[10]: 6

Max Heap mit Tupeln in Python ermitteln

Möglicherweise möchten wir eine Prioritätswarteschlange mit Tupeln statt nur mit Zahlen implementieren. Da die Tupel von Python unveränderlich sind, ist dies eine Herausforderung für die Aufgabe, die Prioritätszahl mit -1 zu multiplizieren.

Die Lösung besteht darin, jedes Tupel zunächst in eine Liste umzuwandeln, das erste Element dieser Unterlisten um -1 zu modifizieren, sie wieder in Tupel umzuwandeln und gleichzeitig eine neue Liste mit diesen Tupeln zu erstellen. Die neue Liste wird dann mit heapify() in einen Heap umgewandelt.

Um den Maximalwert abzurufen, verwenden wir heappop() auf dem Heap, wandeln das Tupel in eine Liste um, ändern das erste Element, um einen positiven Wert zu erhalten, und wandeln die Liste dann wieder in ein Tupel um.

Beispielcode:

# Max Heap With Tuples

# Make a list of tuples.
l = [(1, "A"), (5, "B"), (3, "C"), (7, "D"), (6.5, "E")]
# View the list.
l

# Create an empty list to hold modified tuples.
l_max = []

# Populate the list with modified tuples.
for i in range(len(l)):
    j = list(l[i])
    j[0] = -1 * j[0]
    l_max.append(tuple(j))

# View the modified list.
l_max

# Create the min heap.
heapq.heapify(l_max)

# View the min-heap.
l_max

# Create a function that uses meappop and
# changes the number back to a positive value.


def maxpop(mh):
    l = list(heapq.heappop(mh))
    l[0] = -1 * l[0]
    return tuple(l)


# Test the values popped by the maxpop.
# RUN ONE LINE AT A TIME.
maxpop(l_max)
maxpop(l_max)
maxpop(l_max)

Ausgabe:

l
Out[15]: [(1, 'A'), (5, 'B'), (3, 'C'), (7, 'D'), (6.5, 'E')]

l_max
Out[14]: [(-1, 'A'), (-5, 'B'), (-3, 'C'), (-7, 'D'), (-6.5, 'E')]

heapq.heapify(l_max)

l_max
Out[17]: [(-7, 'D'), (-6.5, 'E'), (-3, 'C'), (-5, 'B'), (-1, 'A')]

maxpop(l_max)
Out[19]: (7, 'D')

maxpop(l_max)
Out[20]: (6.5, 'E')

maxpop(l_max)
Out[21]: (5, 'B')

Andere benötigte Heap-Funktionen können unter Verwendung der gleichen Techniken implementiert werden.

Verweise

Weitere Details und Beispiele finden Sie in der Dokumentation des heapq-Moduls von Python.

Das Python-Entwicklungsteam hat entschieden, keine Max-Heap-Funktionen zu implementieren. Sie können die Funktionsanfrage und die Antwort hier lesen.