[For competition pros] Priority queue (heapq) Summary

When to use

  1. When extracting the maximum / minimum element quickly each time under the condition that the element is added later.
  2. 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

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

Other operations

image

image.png

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.

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

Recommended Posts

[For competition pros] Priority queue (heapq) Summary
Binary search summary for competition professionals
[For competition professionals] Run-length compression summary
[For competition professionals] Summary of doubling
[For competition professionals] Minimum spanning tree summary
[For competition professionals] Union Find Tree Summary
Summary for learning RAPIDS