educative.io

Educative

Why does it heappush -nums[i]?

why does it heappush -nums[i] instead of just nums[i] in the first place?

Is it because heappush and heappop only support minHeap by default? Then is there any option to use it as a maxHeap?

Doing things with negative values seems a little bit weird to my eyes. Isn’t it?


Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5696381570252800

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.

Thanks a lot!