Overloading the __lt__ operator

Courses
,
1

Note really a question, rather an observation. Seems like flipping the lt operator is a little hacky to convert the heapq into a max-heap.

If you’d want to use the Point class in a min-heap, then this change breaks the interface.

Alternatively, you can just negate the distance of the first k points and store the corresponding index when pushing to the heap. But in a proper solution it’s preferable to encapsulate this logic in the max-heap itself to flip the lt of the elements it holds (unless you always remember to negate any values being pushed).

def k_closest(points, k):

# push the first k points
heap = [ (-points[i].dist(), i) for i in range(k)]
heapq.heapify(heap)

for i in range(k, len(points)):
    if points[i].dist() < -heap[0][0]:
       heapq.heappop(heap)
       heapq.heappush(heap, (-points[i].dist(), i))

return [points[i] for _, i in heap]

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: https://www.educative.io/courses/grokking-coding-interview-patterns-python/solution-k-closest-points-to-origin

2

Hello @Lars,

Thank you for sharing this interesting observation on the lesson “K Closest Points to Origin”. We’ll get back to you after taking a deeper look on the solution code.

Happy learning!