2.11 Heap & Priority Queue

https://www.educative.io/blog/data-structure-heaps-guide

https://leetcode.com/problems/kth-largest-element-in-a-stream/submissions/1135214913

Here you go:

import heapq
nums = [3, 1, 4, 1, 5, 9, 2, 6] # If you have no starting data, just create an empty list [] and go straight to heappush. 
heapq.heapify(nums)  # Turns a regular list into a minheap, O(n)
heapq.heappush(nums, 7)  # Adds 7 to the heap, O(log(n))
heapq.heappop(nums)  # Removes and returns the smallest element from the top, O(log(n))
heapq.heappushpop(nums, 8)  # Pushes 8 and then pops the smallest item, O(log(n))
heapq.heapreplace(nums, 10)  # Replaces the smallest item with 10, O(log(n))
heapq.nlargest(3, nums)  # Returns the three largest elements
heapq.nsmallest(3, nums)  # Returns the three smallest elements

---

How does heapq return the 3 largest elements, under the hood? §

When you call heapq.nlargest(), it doesn’t exactly construct a traditional max heap and then destroy it. Instead, it uses an efficient approach to find the n largest elements from the given iterable (like a list). Here’s a more detailed, yet simplified explanation of what happens:

1. Partial Heap Construction: The function builds a min heap, but only of size n (the number of largest elements you want to find). It doesn’t create a full max heap of all elements in the list.

2. Heap Maintenance: As it iterates through the list, it compares each element to the smallest element in the min heap (which is at the root of the heap). If the new element is larger than this smallest element, it replaces it and re-adjusts the heap to maintain the min heap property. This is more efficient than maintaining a full max heap.

3. Result Compilation: Once it has gone through all elements, the min heap must contain the n largest elements from the original list. These elements are then extracted and returned, usually in sorted order.

So, heapq.nlargest is an efficient way to find the largest elements without the need to sort the entire list or maintain a full-size heap. It’s particularly efficient when n is much smaller than the total number of elements in the list.

---

What is the time complexity of converting an ordinary list into a minheap, all at once? §

$O(n)$

↳ What is the time complexity of converting an ordinary list into a minheap, one at a time? §

$O(n\cdot log(n))$

---