Wann zu verwenden

Wenn Sie das maximale / minimale Element jedes Mal schnell extrahieren, unter der Bedingung, dass das Element später hinzugefügt wird.
Wenn zwei Bedingungen für die Auswahl eines Elements aus den Optionen vorhanden sind. (Es gibt Elemente, die erst erfasst werden können, wenn die Bedingungen erfüllt sind. Unter diesen wird der Maximal- / Minimalwert erfasst.)

Was ist gut

O (logN) für Push / Pop O (1), um die Anzahl der Elemente und den Mindestwert zu erhalten

Was ist zu tun

Heapq importieren.
Bereiten Sie eine leere Liste vor. oder heapify () eine vorhandene Liste.
Fügen Sie dem Heap mit heappush (heap, item) ein Element hinzu.
Holen Sie sich mit heappop (heap) das minimale Element aus dem Heap.

Andere Operationen

Wenn Sie 2 und 3 gleichzeitig ausführen möchten, können Sie nach dem Drücken auf den Heap mit "heappushpop (heap, item)" ein Pop-up ausführen (dies ist effizienter).
Um auf das kleinste Element zuzugreifen, ohne zu knallen, setzen Sie den Index auf 0 und greifen Sie mit dem Klammeroperator zu.

Bild

Denken

Da der Heap nur den Minimalwert erfassen kann, sollten Sie, wenn Sie den Maximalwert verwenden möchten, alle Elemente im Voraus negativ machen und einfügen. Nehmen Sie nach der Erfassung den Absolutwert und geben Sie ihn zurück.

Vorlage

Für 2 Fälle

def main():
    #Fassen Sie die Optionen für jedes Timing zusammen, sobald es verfügbar ist.

    #Ändern Sie die Bedingungen.
    for n in range(N):
        #Stellen Sie die verfügbaren Optionen in die Warteschlange(Ich möchte den Maximalwert, wenn ich ihn herausnehme, also mache ihn negativ.)

        #Wenn der Heap nicht leer ist, wählen Sie die beste Option und geben Sie ein Minus zurück.

    return

Anwendungsbeispiel

1 Fall

ABC096 B - Maximum Sum

import heapq

def main():
    A, B, C = map(int, input().split())
    K = int(input())

    heap = [-A, -B, -C]
    heapq.heapify(heap)
    for _ in range(K):
        max = heapq.heappop(heap)
        heapq.heappush(heap, max * 2)
    
    sum = 0
    for i in heap:
        sum += i
    print(-sum)

2 Fälle

2. praktischer Algorithmus-Test F - Aufgabenverdauung

import heapq

def main():
    N = int(input())

    #Tag Tag Verwalten Sie alle Optionen, die am Tag ausgewählt werden können.
    tasks = [[] for _ in range(N + 1)]
    for _ in range(N):
        a, b = map(int, input().split())
        tasks[a].append(b)

    heap = []
    points = 0

    for day in range(1, N + 1):
        #Stellen Sie die verfügbaren Optionen in die Warteschlange(Ich möchte den Maximalwert, wenn ich ihn herausnehme, also mache ihn negativ.)
        for i in tasks[day]:
            heapq.heappush(heap, -i)
        #Wenn der Heap nicht leer ist, wählen Sie die beste Option und geben Sie ein Minus zurück.
        if len(heap) > 0:
            points += abs(heapq.heappop(heap))
        print(points)
    return

Das obige ähnliche Thema

ABC137 D - Summer Vacation

Es stehen zwei Bedingungen zur Auswahl.

Belohnungen um M Tage erhalten → Wenn Sie von M Tagen zurückkehren, erhöht sich die Anzahl der Aufgaben, die Sie auswählen können.
Holen Sie sich den Maximalwert unter ihnen
2 Bei der Auswahl aus den Bedingungen ist es besser, mit den strengeren Bedingungen zu beginnen.

import heapq

def main():
    N, M = map(int, input().split())

    #Tag Tag Verwalten Sie alle Optionen, die am Tag ausgewählt werden können.
    jobs = [[] for _ in range(M + 1)]
    for _ in range(N):
        a, b = map(int, input().split())
        if a > M:
            continue
        jobs[a].append(b)

    heap = []
    salary = 0

    #Es geht vom M-Tag zurück.
    for day in range(1, M + 1):
        #Stellen Sie die verfügbaren Optionen in die Warteschlange(Ich möchte den Maximalwert, wenn ich ihn herausnehme, also mache ihn negativ.)
        for i in jobs[day]:
            heapq.heappush(heap, -i)
        #Wenn der Heap nicht leer ist, wählen Sie die beste Option und geben Sie ein Minus zurück.
        if len(heap) > 0:
            salary += abs(heapq.heappop(heap))
    print(salary)
    return

Referenz

https://docs.python.org/ja/3/library/heapq.html

[PYTHON] [Für Wettkampfprofis] Priority Queue (Heapq) Zusammenfassung