Tag Archives: The queue

Python uses the priority queue to get the maximum k elements

Use PriorityQueue to get the maximum K elements
In order to sort slightly larger numbers, sometimes you don’t want all of the data, you just want the maximum k numbers up front, if you use sorted numbers ([…]). )[::-1][:k] Implementation efficiency is much lower. In order to optimize the execution speed, PriorityQueue can be used to achieve the maximum k elements. At the same time, the space can also be significantly optimized

import queue
import random

K = 12
q = queue.PriorityQueue()
tlist = []

for ith in range(100):
    q.put((ith, ith + random.randrange(100)))
    if q.qsize() > K: q.get() # pop least item
        
while not q.empty():
    tnum = q.get()
    tlist.append(tnum)

tlist.sort(reverse=True)
print(tlist)

The effect

[(99, 187), (98, 152), (97, 184), (96, 136), 
(95, 105), (94, 119), (93, 109), (92, 169), 
(91, 149), (90, 143), (89, 91), (88, 92)]

Priorityqueue are in queue bag and priorityqueue implementation in the queue is called headq inside the top of the heap, so did not provide key parameters change priority queue sorting rules, only from small to large, ascending order so, in order to get top K elements, need to queue size is greater than K pop team first element, maintain the biggest K in queue, and then use a list to undertake the element in the queue, and then descending sort results for the target at a time.