Introduction

Glimpse,

class queue.PriorityQueue(maxsize=0) Priority queue constructor. maxsize is an integer that sets an upper limit on the number of elements that can be queued. Once this size is reached, inserts are blocked until the queue elements are consumed. If maxsize is less than or equal to 0, the queue size is infinite.

So queue.PriorityQueue seems to be good from the name. But the queue itself

The queue module implements multi-producer, multi-consumer queues. This is especially useful in multithreaded programming when information must be safely exchanged between multiple threads.

So it's obviously heavy (it seems to have some behavior for synchronization).

What i did

-Prepare an array a consisting of $ 2 \ cdot 10 ^ {5} $ random positive integers ($ \ leq 10 ^ {9} $) --Prepare an array b consisting of another $ 2 \ cdot 10 ^ {5} $ random positive integers ($ \ leq 10 ^ {9} $)

Then do the following $ 2 \ cdot 10 ^ {5} $ times. (This is the i-th operation)

--Take the smallest number from a. Then add the i-th element of b to a

Compare this with heapq and queue. In addition, when doing the above work, heapq is faster using pushpop than popping and pushing, so compare the speed as well.

result

--- Heapq, poppush
elapsed_time:0.15400314331054688[sec]
--- Heapq, pop then push
elapsed_time:0.20299005508422852[sec]
--- Queue
    Step1: create init queue
elapsed_time:0.37195301055908203[sec]
    Step2: pop then push
elapsed_time:0.873100996017456[sec]

So use heapq when using priority queues in Python (in competitive programming). Since queue.PriorityQueue does not have init, it pushes the array a to q, which is created one by one.

code

import queue
import heapq

import time
import random
from copy import deepcopy
n = 2 * 10**5

inqueue = [random.randint(0, 10**9) for _ in range(n)]
inheapq = deepcopy(inqueue)

data = [random.randint(0, 10**9) for _ in range(n)]

resqueue = []
resheapq = []

print("--- Heapq, poppush")
start = time.time()
heapq.heapify(inheapq)
for i in range(n):
    x = heapq.heappushpop(inheapq, data[i])
    resheapq.append(x)
elapsed_time = time.time() - start
print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

print("--- Heapq, pop then push")
start = time.time()
heapq.heapify(inheapq)
for i in range(n):
    x = heapq.heappop(inheapq)
    resheapq.append(x)
    heapq.heappush(inheapq, data[i])
elapsed_time = time.time() - start
print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

print("--- Queue")
print("    Step1: create init queue")
start = time.time()
q = queue.PriorityQueue(n)
start = time.time()
for i in range(n):
    q.put(inqueue[i])
elapsed_time = time.time() - start
print("elapsed_time:{0}".format(elapsed_time) + "[sec]")
print("    Step2: pop then push")
start2 = time.time()
for i in range(n):
    x = q.get()
    resqueue.append(x)
    q.put(data[i])
elapsed_time = time.time() - start2
print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Is the priority queue heapq in Competitive Pro (Python)? queue.PriorityQueue? Which one should I use?

Introduction

What i did

result

code