이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 자료구조 — 효율적인 데이터 관리의 핵심 → 자료구조 — 효율적인 데이터 관리의 핵심 → 트리와 그래프
Min/max heap structure, heapify, heap sort, priority queue, Dijkstra connection, Top-K, streaming median.
Min-Heap: Max-Heap:안녕하세요, 오늘은 힙이라는 특별한 자료구조를 배워볼게요.
그림을 보면 왼쪽에 최소 힙, 오른쪽에 최대 힙이 나란히 있어요.
힙은 완전 이진 트리인데, 여기에 부모-자식 간 순서 규칙이 추가된 거예요.
최소 힙에서는 부모가 항상 자식보다 작거나 같아요.
그래서 왼쪽 트리 꼭대기, 루트를 보면 가장 작은 값 1이 있죠.
반대로 최대 힙은 부모가 자식보다 크거나 같아서 루트가 10이에요.
중요한 건 형제끼리는 순서가 없다는 거예요.
왼쪽 자식이 오른쪽보다 작을 수도, 클 수도 있어요.
이건 이진 탐색 트리와 결정적으로 다른 점이에요.
이진 탐색 트리는 왼쪽이 항상 작고 오른쪽이 크지만, 힙은 그렇지 않아요.
그림 아래쪽 배열 표현을 보세요.
힙은 트리이지만 실제로는 배열 하나로 저장돼요.
레벨 순서대로 왼쪽에서 오른쪽으로 배열에 넣으면 되거든요.
완전 이진 트리라서 빈 공간이 없어요 — 배열에 딱 맞아떨어져요.
최소 힙의 가장 큰 장점은 최솟값을 O(1)에 바로 꺼낼 수 있다는 거예요.
배열의 0번 인덱스가 곧 루트니까요.
삽입과 삭제는 O(log n)이에요 — 트리 높이만큼만 이동하면 돼요.
왜 힙이 필요할까요? 매번 최솟값이나 최댓값이 필요한 상황이 많아요.
예를 들어 응급실에서 가장 급한 환자를 먼저 치료하는 것처럼요.
정렬된 배열로도 되지만 삽입이 O(n)이라 힙이 훨씬 효율적이에요.
이제 힙이 어떻게 배열로 구현되는지 자세히 알아볼게요.
선생님: 힙에서 형제 노드끼리 크기 순서가 보장되나요?
학생: 아니요, 힙은 부모-자식 관계만 보장하고 형제 간에는 순서가 없어요.
선생님: 맞아요. 그렇다면 왜 이진 탐색 트리 대신 힙을 쓸까요?
학생: 힙은 최솟값이나 최댓값을 O(1)에 바로 알 수 있어서요.
선생님: 정확해요! 이진 탐색 트리는 최솟값을 찾으려면 왼쪽 끝까지 가야 해서 O(log n)이에요.
학생: 그리고 힙은 완전 이진 트리라 배열로 효율적으로 저장할 수 있잖아요.