힙(Heap)이란?
힙은 완전 이진 트리의 형태로 만들어진 자료구조를 말하며
우선순위 큐를 위해 만들어졌다.
여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어져 있다.
완전 이진 트리란?
마지막 레벨을 제외한 모든 노드가 꽉 채워진 트리 구조를 말한다.
힙 vs 이진 탐색 트리
힙은 우선순위 키 정렬에,
이진 탐색 트리는 탐색에 강점을 지닌 자료구조이다.
힙의 종류
최대 힙과 최소 힙이 있다.
- 최대 힙: 완전 이진트리이며 부모 노드가 자식 노드보다 크다.
- 최소 힙: 완전 이진트리이며 부모 노드가 자식 노드보다 작다.
보통 힙이라고 하면 최대 힙을 말한다.
힙 정렬의 예시
힙 정렬이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법으로서,
내림차순 정렬을 위해선 최대 힙을 구성하고
오름차순 정렬을 위해선 최소 힙을 구성하면 된다.
힙 삽입과 삭제를 통해 힙을 구성할 수 있는데,
값 삽입(삭제) >> 힙 구조 변경 >> 값 삽입(삭제) >> 힙 구조 변경
이 과정을 반복하면 된다.
4 7 2 9 8 5 1
이런 숫자의 모음으로 힙을 만들어보자.
그림이 좀 못생겼는데...
일단 힙에서 자식 노드는 힙마다 다르긴 하지만 보통 2개를 갖는다.
주어진 숫자를 하나씩 트리에 넣었을 때
자식 노드가 부모 노드보다 크다면 위치를 바꿔주는 작업을 한다.
즉 삽입 >> 힙 구조 변경, 이 과정을 반복하는 것이다.
최소 힙의 경우 작은 수가 위로 올라간다고 생각하면 되며
같은 노드끼리 크기 비교는 하지 않는다.
그리고 힙의 삭제를 통해 구현하려면
마찬가지로 루트 노드인 최상단 부모 노드부터 삭제를 하는데
이때는 최대 힙의 가장 마지막 노드를 가져와 루트 자리에 넣는다.
이후론 마찬가지로 부모와 자식 노드 간의 크기 비교를 통해
힙 구조를 변경하는 방식이다.
아래 그림을 참고하자.
시간복잡도
이진 트리를 최대 힙으로 만들기 위해 재구성하는 과정이 트리의 깊이만큼 이루어지므로 O(log n)의 시간이 걸리고,
구성된 최대 힙으로 힙 정렬을 수행하는 데 걸리는 전체 시간은
힙 구성시간과 n개의 데이터 삭제 및 재구성 시간을 포함한다.
따라서 일반적인 힙 정렬의 시간복잡도는 O(n log n)을 갖는다.
