목차
- 힙 이란?
- 힙 정렬이란?
- 힙 사용 예시
- 힙 정렬 사용 예시
- 시간 복잡도
1. 힙 이란?
최댓값 혹은 최솟값을 빠르게 찾아내기 위해 고안된 완전 이진 트리입니다.
원소 혹은 노드 A, B가 서로 부모 관계일 경우 A와 B는 대소 관계가 적용 됩니다.
최대 힙을 찾는 경우 노드 A가 B의 부모일 경우 항상 A는 B보다 큰 값을 가집니다.
2. 힙 정렬이란?
최대 힙이나 최소 힙을 이용하여 정렬하는 방식입니다.
오름차순 정렬을 할려면 최대 힙을, 내림차순 정렬을 할려면 최소 힙을 구해야 합니다.
3.힙 사용 예시
다음의 배열을 이용해 최대 힙을 만들어 보겠습니다.
배열을 완전 이진 트리로 표현하게 될 경우 위 그림과 같이 표현할 수 있습니다.
이렇게 표현하게 될 경우 연산하기 편한 장점이 있습니다.
부모 노드의 위치를 i라고 할 때 왼쪽 자식 노드를 i * 2 + 1, 오른쪽 자식 노드를 i * 2 + 2로 표현할 수 있습니다.
또한 배열의 절반 앞부분(0~4)노드는 부모 노드인 것을 확인할 수 있습니다.
부모 노드의 끝부분 부터 루트까지 다음과 같은 과정을 거칩니다.
리프 노드에서부터 부모 노드가 자식 노드보다 작으면 값을 바꿔주는 과정을 거칩니다.
루트 노드부터 진행하지 않는 이유는 리프 노드부터 루트 노드까지 아래부터 위로 바꿔나가면 한번만에 이 과정을 끝낼 수 있기 때문입니다.
위 과정에서는 swap이 발생하지 않습니다.
하지만 바로 위의 노드에서는 swap이 발생합니다.
이런 과정을 루트에 도달할 때까지 진행하면 다음과 같은 모습이 됩니다.
위 그림에서 확인할 수 있듯이 루트에 최댓값 10이 존재하는 것을 확인할 수 있습니다.
4. 힙 정렬 사용 예제
방금 위 과정으로 최댓값을 찾았습니다.
힙 과정을 거칠 때마다 루트 노드에 최댓값을 가지게 됩니다.
힙 과정을 한번 거친 후에 루트와 배열 마지막 노드를 바꿔줍니다.
이후에 마지막 노드를 고정하고 이 노드를 제외한 배열로 또다시 힙을 진행합니다.
1. 힙을 진행해 최댓값을 찾는다.
2. 찾은 최댓갑을 제외하고 위치를 고정합니다.
이 과정을 노드의 갯수만큼 반복합니다.
이후의 과정은 생략하겠습니다.
5. 시간 복잡도시간 복잡도
최대 힙을 찾는 시간은 log(N)이며, 이 과정을 N번 반복합니다.
그렇기 때문에 힙 정렬의 과정은 N * log(N)입니다.
