힙(Heap) 자료구조를 통해 배우는 효율적인 알고리즘
최근 MIT 강의를 듣다가 힙(Heap)이라는 자료구조를 접하게 되었는데, 그 우아함에 깜짝 놀랐다. 이 녀석이 왜 "귀여운 자료구조"라고 불리는지 알 것 같더라.
"One of the cutest little data structures that was ever invented is called the heap."
1. 힙은 단순한 배열인데, 이를 '완전 이진 트리'로 시각화한다
정말 신기한 게, 그냥 일차원 배열을 트리 형태로 생각하는 거다. 배열의 인덱스 관계가 이렇게 정의된다:
루트: A[1]
부모: A[i/2]
왼쪽 자식: A[2i]
오른쪽 자식: A[2i+1]
이게 무슨 마법인가 싶었는데, 실제로 써보니 정말 직관적이다. 복잡한 포인터나 링크 없이도 트리를 만들 수 있다니!
2. Max-heap의 핵심은 단 하나의 규칙이다
"부모는 항상 자식보다 크거나 같다"
"The key of a node is greater than or equal to the keys of its children."
단순하지만 이 하나의 규칙으로 엄청난 일을 할 수 있다. 최대값을 찾는 건 O(1)이 된다. 그냥 루트만 보면 되니까!
3. Heapify - 한 번의 위반을 고치는 마법
Max-heapify는 정말 영리한 알고리즘이다. 전체 트리가 엉망이어도 괜찮다. 한 노드에서만 문제가 있으면, 그것만 고쳐준다.
과정은 간단하다:
자신과 두 자식 중 가장 큰 값 찾기
필요하면 자리 바꾸기
자식 쪽에서 문제가 생기면 재귀적으로 반복
시간 복잡도는 O(log n). 왜냐하면 트리의 높이만큼만 내려가면 되니까.
4. Build-max-heap - 신기한 순서의 비밀
정말 놀라운 건 이 부분이었다. 무작정 배열을 힙으로 만들 때, 어디서부터 시작할까?
for i = n/2 down to 1:
max-heapify(A, i)
n/2부터 시작하는 이유가 너무 영리했다. 그 이후는 모두 leaf 노드들이라 이미 max-heap 조건을 만족하기 때문이다!
5. 복잡도 분석의 함정과 통찰
처음에는 "O(n) 번의 max-heapify 호출 × O(log n) = O(n log n)"이라고 생각했다. 하지만 실제로는 O(n)이다!
위에 있는 노드일수록 더 많은 작업을 하지만, 노드 수가 적다. 아래로 갈수록 노드는 많지만 작업은 적다. 이 trade-off 때문에 전체적으로는 linear time이 나온다.
"But there are fewer and fewer nodes as you get higher and higher up"
진짜 수학적으로 계산해보면, 기하급수 수렴으로 증명된다. 아름답다!
6. Heap Sort - 우아한 정렬의 완성
결국 이 모든 게 정렬을 위한 준비였다:
1) Build-max-heap (O(n))
2) 최대값을 맨 뒤로 보내고 힙 크기 줄이기
3) Max-heapify로 복구 (O(log n))
4) 2-3번을 n번 반복
총 시간 복잡도: O(n log n)
7. 깨달은 점
이 강의를 보면서 느낀 건, 좋은 알고리즘은 단순한 아이디어에서 시작한다는 것이다. 배열을 트리로 보는 시각, 한 노드씩 고치면서 올라가는 방식, 그리고 정확한 시작점을 찾는 통찰.
또한 복잡도 분석도 단순히 worst case만 보면 안 되고, 실제 분포를 잘 따져봐야 한다는 교훈도 얻었다.
"It is not any more complicated than this. There may be many steps."
단순하지만 강력하다. 이게 바로 좋은 알고리즘의 특징이 아닐까? 앞으로도 이런 우아한 해결책을 더 많이 배우고 싶다. 누군가에게 이 정리가 도움이 되길 바라며 :)
