PYTHON
Find K Largest Elements Using Heapq
Discover how to efficiently retrieve the 'k' largest elements from a list or stream of data using Python's `heapq` module, implementing a min-heap strategy.
import heapq
def find_k_largest_elements(numbers, k):
if k <= 0:
return []
if k >= len(numbers):
return sorted(numbers, reverse=True)
# Create a min-heap of size k
# The heap will store the k largest elements seen so far
# but in min-heap order (smallest of the k at the root)
min_heap = []
for num in numbers:
if len(min_heap) < k:
heapq.heappush(min_heap, num)
elif num > min_heap[0]: # If current number is larger than the smallest in heap
heapq.heappop(min_heap) # Remove smallest
heapq.heappush(min_heap, num) # Add current number
# The heap now contains the k largest elements.
# To get them in descending order, pop them one by one or sort the heap.
return sorted(min_heap, reverse=True)
# Example usage:
data = [3, 2, 1, 5, 6, 4, 7, 8, 9, 0]
k_val = 3
largest_elements = find_k_largest_elements(data, k_val)
# Expected output: [9, 8, 7]
# print(f"Original list: {data}")
# print(f"{k_val} largest elements: {largest_elements}")
How it works: This snippet uses Python's `heapq` module to efficiently find the `k` largest elements in a list. It maintains a min-heap of size `k`. For each number in the input list, if the heap size is less than `k`, the number is added. If the heap is full and the current number is greater than the smallest element in the heap (the root), the smallest element is removed, and the current number is added. This ensures the heap always contains the `k` largest elements encountered so far. Finally, the heap is sorted in reverse to present the results in descending order.