[Neetcode/Heap] K Closest Points to Origin

https://neetcode.io/problems/k-closest-points-to-origin

NeetCode

---

큐(Queue)는 선입선출(First In, First Out, FIFO)의 자료 구조로, 먼저 들어온 데이터가 먼저 나간다. 하지만 우선순위가 있는 작업에서는 큐의 기본 원칙을 따르지 않을 때가 있다. 우선순위 큐(Priority Queue) 는 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료 구조다.

힙( Heap)이란?

힙(Heap)은 우선순위 큐를 구현하기 위한 자료 구조다. 힙의 뜻을 살펴보면, "쌓아 올린 더미" 또는 "쌓아 올리다"라는 의미를 가진다. 힙은 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 한며, 다음과 같은 규칙을 따른다.

규칙 1: 노드를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간다. (레벨 순서로 노드를 삽입한다.)

• 위 그림은 모두 이진트리인데, (a)는 힙이지만 (b)는 힙이 아니다.
• (b)는 왼쪽부터 채워야 한다는 규칙을 벗어났다.

규칙 2: 최소 힙은 부모 노드가 자식 노드의 값보다 작거나 같아야 한다. 파이썬의 heapq 모듈은 최소 힙(min heap)이다. (최대 힙은 부모 노드가 자식 노드의 값보다 크거나 같다.)

• (a)는 힙이지만, (b)는 힙이 아니다.
• (b)는 부모 노드인 5가 자식 노드인 4보다 크다.

(+) Min Heap vs Max heap

• Min Heap: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• Max Heap: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

https://www.geeksforgeeks.org/heap-data-structure/minheapandmaxheap

파이썬의 heapq 모듈 구현하기

파이썬에서는 heapq 모듈은 배열(리스트)을 이용하여 완전 이진트리를 구현한다. 완전 이진트리는 왼쪽부터 빈 공간 없이 차례대로 채워지기 때문에, 배열을 이용하여 효율적으로 관리할 수 있다.

직접 구현할 최소 힙도 배열을 이용하여 만든다. 아래 메서드를 활용하여 배열로 인덱스를 조작하기만 하면 된다. 

• heappush(heap, data): 힙에 새로운 데이터를 삽입한다.
• heappop(heap): 힙에서 루트 노드(최소값)를 꺼낸 후 삭제한다.
• heapify(x): 주어진 배열을 힙 구조로 변환한다.

(* 출처: https://wikidocs.net/194445)

08장 파이썬으로 힙(heap) 구현하기

(출처: https://littlefoxdiary.tistory.com/3)

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

---

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # Min-heap to store (distance squared, point)
        heap = []
        for x, y in points:
            dist = x * x + y * y  # No need to take square root
            heapq.heappush(heap, (dist, [x, y]))
        
        # Extract k closest points
        return [heapq.heappop(heap)[1] for _ in range(k)]

✅ What are we pushing?

We push a tuple:

(dist, [x, y])

• dist is the squared distance from the origin.
• [x, y] is the actual point.
• The heap will automatically sort by the first item in the tuple (dist), so the smallest distance will always be at the top.

🧹 return [heapq.heappop(heap)[1] for _ in range(k)]

This is a list comprehension that runs k times. Here's what it's doing:

1. heapq.heappop(heap):
   • Pops (removes and returns) the smallest element in the heap (i.e., the closest point so far).
   • The element is a tuple: (dist, [x, y]).
2. [1]:
   • Grabs just the [x, y] part from the tuple, which is at index 1.
3. The list comprehension runs k times, so it collects the k closest points to the origin.

🧠 Putting it all together:

heapq.heappush(heap, (dist, [x, y]))

➡️ Adds each point to the heap, sorted by distance.

[heapq.heappop(heap)[1] for _ in range(k)]

➡️ Pops the k smallest-distance points (i.e., k closest points to the origin).