When to use

When extracting the maximum / minimum element quickly each time under the condition that the element is added later.
When there are two conditions for selecting an element from the options. (There are elements that cannot be acquired until the conditions are met. Among them, the maximum / minimum values are acquired.)

What is good

O (logN) for push / pop O (1) to get the number of elements and the minimum value

What to do

ʻimport heapq`.
Prepare an empty list. or heapify () an existing list.
Add an element to the heap with heappush (heap, item).
Get the minimum element from the heap with heappop (heap).

Other operations

If you want to do 2 and 3 at the same time, you can pop after pushing to the heap with heappushpop (heap, item) (this is more efficient).
If you want to access the smallest element without popping, set the index to 0 and access with the bracket operator.

image

Thinking

Since the heap can only acquire the minimum value, if you want to take the maximum value, make all the elements negative in advance and plunge into it, and after acquisition, take the absolute value and return it.

template

For 2 cases

def main():
    #Summarize the options for each timing when it becomes available.

    #Change the conditions.
    for n in range(N):
        #Enqueue the choices that will be available(I want the maximum value when I take it out, so make it negative.)

        #If the heap is not empty, get the best option and return a minus.

    return

Example of use

1 case

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 cases

2nd Algorithm Practical Test F-Task Digestion

import heapq

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

    #Day day Manage all the options that can be selected on the day.
    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):
        #Enqueue the choices that will be available(I want the maximum value when I take it out, so make it negative.)
        for i in tasks[day]:
            heapq.heappush(heap, -i)
        #If the heap is not empty, get the best option and return a minus.
        if len(heap) > 0:
            points += abs(heapq.heappop(heap))
        print(points)
    return

The above similar subject

ABC137 D - Summer Vacation

There are two conditions to select.

Get rewards by M days → If you go back from M days, you can select more tasks.
Get the maximum value among them
2 When selecting from the conditions, it is better to start with the stricter conditions.

import heapq

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

    #Day day Manage all the options that can be selected on the day.
    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

    #It goes back from the M day.
    for day in range(1, M + 1):
        #Enqueue the choices that will be available(I want the maximum value when I take it out, so make it negative.)
        for i in jobs[day]:
            heapq.heappush(heap, -i)
        #If the heap is not empty, get the best option and return a minus.
        if len(heap) > 0:
            salary += abs(heapq.heappop(heap))
    print(salary)
    return

reference

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

[PYTHON] [For competition pros] Priority queue (heapq) Summary