Hi @conga,
The heappush
function from the python heapq
library automatically maintains the heap property
or heap invariant
. This property states that the parent node has to be smaller than the children nodes.
We know that the largest positive number becomes the smallest negative number, so using heappush(maxHeap, -nums[i])
ensures that the largest of the k elements is at the root or index 0
of our array and the rest of the numbers are smaller, so we have the kth smallest element at the root of our heap.
We then check if any of the remaining numbers is smaller with the -nums[i] > maxHeap[0]
check. Using this check, we can replace the kth
largest element using heappop
and heappush
, which will ensure that the smallest (which in actuality is the largest) among the k elements is at the index 0
. In the end, we return -maxHeap[0]
, which returns the value in its original form.
It may seem a bit weird to the human eye, but the logic works perfectly, simply because the heappush
function maintains the heap invariant
.
I hope this was helpful.