<\/p>\n\n\n\n
When solving problems like \u201cfind the top K largest elements\u201d<\/strong>, you have two common strategies:<\/p>\n\n\n\n At first glance, it may seem both approaches are similar \u2014 especially since we’re just storing K elements \u2014 but their performance and behavior<\/strong> differ significantly.<\/p>\n\n\n\n Say you’re scanning a list or stream of numbers like this:<\/p>\n\n\n\n Now you want to insert a new number: Let\u2019s compare what happens in both approaches.<\/p>\n\n\n\n Current list:<\/strong><\/p>\n\n\n\n Insert 4 (maintain sort):<\/strong><\/p>\n\n\n\n If you’re only allowed to store 3 elements (Top K), you’d remove the smallest (now at the start) \u2192 back to We store the smallest<\/strong> of the top K at the root.<\/p>\n\n\n\n Heap (min-heap) contents (internally):<\/strong><\/p>\n\n\n\n Insert 4:<\/strong><\/p>\n\n\n\n Or if 4 were bigger:<\/p>\n\n\n\n You might ask :<\/p>\n\n\n\n \u201cIf we already have a sorted list of K items, shouldn’t insert be fast?\u201d<\/p>\n<\/blockquote>\n\n\n\n The answer is:<\/p>\n\n\n\n On the other hand, min-heaps<\/strong>:<\/p>\n\n\n\n Use a min-heap<\/strong> ( Use a sorted list<\/strong> when:<\/p>\n\n\n\n When solving problems like \u201cfind the top K largest elements\u201d, you have two common strategies: At first glance, it may seem both approaches are similar \u2014 especially since we’re just storing K elements \u2014 but their performance and behavior differ significantly. \ud83d\udd0d Scenario: Maintain Top 3 Elements Say you’re scanning a list or stream of numbers like this: […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-97","post","type-post","status-publish","format-standard","hentry","category-python-blog"],"_links":{"self":[{"href":"https:\/\/www.alerainfotech.com\/home\/wp-json\/wp\/v2\/posts\/97","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.alerainfotech.com\/home\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.alerainfotech.com\/home\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.alerainfotech.com\/home\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.alerainfotech.com\/home\/wp-json\/wp\/v2\/comments?post=97"}],"version-history":[{"count":2,"href":"https:\/\/www.alerainfotech.com\/home\/wp-json\/wp\/v2\/posts\/97\/revisions"}],"predecessor-version":[{"id":110,"href":"https:\/\/www.alerainfotech.com\/home\/wp-json\/wp\/v2\/posts\/97\/revisions\/110"}],"wp:attachment":[{"href":"https:\/\/www.alerainfotech.com\/home\/wp-json\/wp\/v2\/media?parent=97"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.alerainfotech.com\/home\/wp-json\/wp\/v2\/categories?post=97"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.alerainfotech.com\/home\/wp-json\/wp\/v2\/tags?post=97"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\n
heapq<\/code>) to do the same<\/li>\n<\/ol>\n\n\n\n
\n\n\n\n\ud83d\udd0d Scenario: Maintain Top 3 Elements<\/h3>\n\n\n\n
[5, 6, 7]
<\/code><\/pre>\n\n\n\n4<\/code><\/p>\n\n\n\n
\n\n\n\n\u2705 Method 1: Sorted List Approach<\/h2>\n\n\n\n
[5, 6, 7]
<\/code><\/pre>\n\n\n\n\n
O(log K)<\/code><\/li>\n\n\n\n4<\/code> at index 0 \u274c requires shifting all elements right \u2192 O(K)<\/code><\/li>\n<\/ol>\n\n\n\n\ud83d\udd27 Result:<\/h3>\n\n\n\n
[4, 5, 6, 7]
<\/code><\/pre>\n\n\n\n[5, 6, 7]<\/code><\/p>\n\n\n\n\u23f1 Complexity:<\/h3>\n\n\n\n
\n
O(log K)<\/code><\/li>\n\n\n\nO(K)<\/code><\/li>\n\n\n\n
\n\n\n\n\u2705 Method 2: Min-Heap Approach<\/h2>\n\n\n\n
[5, 6, 7]
<\/code><\/pre>\n\n\n\n\n
heap[0]<\/code> (which is 5)<\/li>\n\n\n\n4 < 5<\/code>, we don\u2019t insert<\/strong> \u2192 discard \u2705 O(1)<\/code><\/li>\n<\/ul>\n\n\n\n\n
heapq.heappushpop()<\/code> \u2192 \u2705 O(log K)<\/code><\/li>\n<\/ul>\n\n\n\n
\n\n\n\n\ud83d\udd27 Visual Example:<\/h3>\n\n\n\n
Heap Structure (before insert):<\/h4>\n\n\n\n
5
\/ \\
6 7
<\/code><\/pre>\n\n\n\nAttempt to insert
4<\/code>:<\/h4>\n\n\n\n\n
4 < 5<\/code> \u2192 too small \u2192 discard<\/li>\n<\/ul>\n\n\n\nAttempt to insert
8<\/code>:<\/h4>\n\n\n\n\n
5<\/code> \u2192 bubble 8<\/code> down \u2192 maintain heap order<\/li>\n<\/ul>\n\n\n\n
\n\n\n\n\ud83d\udd01 Comparison Summary<\/h2>\n\n\n\n
Feature<\/th> Sorted List<\/strong><\/th> Min-Heap ( heapq<\/code>)<\/strong><\/th><\/tr><\/thead>Insert position search<\/td> \u2705 O(log K)<\/code><\/td>\ud83d\udeab Not needed<\/td><\/tr> Insertion (actual shift)<\/td> \u274c O(K)<\/code><\/td>\u2705 O(log K)<\/code><\/td><\/tr>Overall insert cost<\/td> \u274c O(K)<\/code><\/td>\u2705 O(log K)<\/code><\/td><\/tr>Space complexity<\/td> \u2705 O(K)<\/code><\/td>\u2705 O(K)<\/code><\/td><\/tr>Maintains sorted order<\/td> \u2705 Yes<\/td> \u274c No (only top element known)<\/td><\/tr> Best for…<\/td> Small K, final output<\/td> Large streams, fast updates<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\n\n\n\n\u2705 Final Thoughts (Answering Your Original Doubt)<\/h2>\n\n\n\n
\n
\n
O(log K)<\/code> via binary search)<\/li>\n\n\n\nO(K)<\/code>), because all items after the insert point must shift right<\/strong> in memory (Python uses arrays, not linked lists)<\/li>\n<\/ul>\n\n\n\n\n
O(log K)<\/code>)<\/li>\n\n\n\n
\n\n\n\n\ud83e\uddea Optional Code (Min-Heap Top K Tracker)<\/h2>\n\n\n\n
import heapq
class TopKHeap:
def __init__(self, k):
self.k = k
self.heap = []
def add(self, num):
if len(self.heap) < self.k:
heapq.heappush(self.heap, num)
elif num > self.heap[0]:
heapq.heappushpop(self.heap, num)
def get_top_k(self):
return sorted(self.heap, reverse=True)
<\/code><\/pre>\n\n\n\n
\n\n\n\n\u2705 In Summary<\/h2>\n\n\n\n
heapq<\/code>) when:<\/p>\n\n\n\n\n
\n