힙 정렬(Heap Sort)
힙 정렬의 힙은 무엇이고, 어떻게 빠르게 정렬될 수 있는걸까?
힙(Heap)이란, 어떤 자료구조일까?
힙 정렬을 알아보기 전에, 힙이라는 자료구조에 알아보고자 한다. 만약 힙 자료구조에 대해 잘 알고 있다면, 이후의 힙 정렬부터 글을 읽어도 좋을 것 같다. 혹시라도 힙 자료구조에 대해 애매하게 알고 있다면 같이 확실하게 알아보자.
완전 이진 트리(Complete Binary Tree)
힙은 완전 이진 트리(Complete Binary Tree)의 일종인 자료구조다. 그래서 힙을 알기 위해서는 완전 이진 트리에 대해서도 알아야한다. 그럼 이진 탐색 트리란 뭘까?
완전 이진 트리의 구조
- 완전 이진 트리(Complete Binary Tree)
- 부모노드 밑에 자식 노드가 최대 2개까지 있을 수 있고, 마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워져 있는 트리구조
만약 트리를 모르거나, 이 완전 이진 트리의 설명으로 이해하기 어렵다면 트리를 먼저 공부하는 것을 권한다.
힙 속성
힙은 이러한 완전 이진 트리에 힙 속성을 가지는 구조인데, 그렇다면 힙 속성은 무엇일까? 힙 속성은 부모 노드와 자식 노드 간의 관계를 정의하는 규칙으로 2가지(최대힙, 최소힙) 종류가 있다. 이 2가지의 속성 중 하나만 만족하면 된다.
최대 힙(Max Heap)
최대 힙의 구조
- 최대 힙
- 부모 노드의 값은 항상 자식 노드 보다 크거나 같아야한다.(부모 노드 >= 자식 노드)
- 그렇기 때문에 루트 노드에는 항상 가장 큰 값이 위치한다.(루트 노드 = 최대 값)
최소 힙(Min Heap)
최소 힙의 구조
- 최소 힙
- 부모 노드의 값이 자식 노드보다 작거나 같아야한다.(부모 노드 <= 자식 노드)
- 그렇기 때문에 루트 노드에는 항상 가장 작은 값이 위치한다.(루트 노드 = 최소 값)
힙의 데이터 입출력
힙에 데이터 입출력시에도 완전 이진 트리 구조와 힙의 속성을 유지해야 하는데, 이러한 연산을 Heapify라고 한다.
- Heapify
- 힙 속성 유지 과정으로, 완전 이진 트리 구조와 힙의 속성을 유지하는 것을 의미한다.
이러한 힙 속성 유지하면서 어떻게 데이터의 입출력이 있을까?
데이터 삽입(Insert)
힙에서 insert하는 과정
우리가 추가하고싶은 값이 60을 추가하려고 한다면,
- 힙의 마지막 위치에 노드를 추가한다.
- 완전 이진 트리 속성을 유지해야하므로, 마지막 위치에 노드를 먼저 추가한다.
- 부모 노드와 비교하며, 상향 연산을 수행한다.
- 힙 속성을 유지해야하므로, 값을 비교하며 상향 연산을 수행한다.
- 최대 힙이였다면 추가한 값이 부모보다 크다면 교환, 최소 힙이였다면 추가한 값이 부모도가 작으면 교환
데이터 삭제(Extract)
힙에서 extract하는 과정
우리가 꺼내고 싶은 값이 루트 노드(최대값, 혹은 최소값)라고 한다면,
- 루드 노드를 제거한다.
- 힙의 마지막 노드를 루트로 이동시킨다.
- 완전 이진 트리 속성을 유지해야하므로, 루트 노드 위치에 마지막 노드를 이동시킨다.
- 자식 노드와 비교하며, 하향 연산을 수행한다.
- 힙 속성을 유지해야하므로, 값을 비교하며 하향 연산을 수행한다.
- 최대 힙이였다면 더 큰 자식과 교환, 최소 힙이였다면 더 작은 자식과 교환
힙 정렬
지금까지 힙에 대해 알아봤다면, 이 힙을 이용해 정렬하는 방법에 대해 알아보자.
- 힙 정렬
- 힙 정렬(Heap Sort) 은 힙(Heap) 자료구조를 이용해 정렬하는 알고리즘
- 최대 힙을 이용해 내림차순 정렬을 하거나, 최소 힙을 이용해 오름차순 정렬을 한다.
- 시간 복잡도는 O(n log n)이다.
- 최대 힙을 이용해 내림차순 정렬을 하거나, 최소 힙을 이용해 오름차순 정렬을 한다.
이런 힙 정렬의 단계는 2단계로 이루어져 있는데
- 힙 구성
- 주어진 배열을 힙의 구조(=완전 이진 트리)로 구성 -> Heapity 연산
- 힙 정렬
- 힙에서 최대 값이나 최소 값을 꺼내며 정렬 수행
각 과정에 대해 상세히 알아보자.
build heap
완전 이진 트리로 구성
먼저 배열 데이터가 있을 때, 이를 힙 정렬로 정렬한다고 가정하자. 그러면 이 배열 데이터를 완전 이진 트리의 구조로 형태를 변경해야한다.
완전 이진 트리 규칙 배열의 인덱스를 기준으로 부모-자식 관계를 정하는 규칙으로, 이를 통해 변경하면 된다.
- 부모 노드의 인덱스: i-1 / 2
- 왼쪽 자식의 인덱스: 2*i + 1
- 오른쪽 자식의 인덱스: 2*i + 2
예시 데이터로 [4, 10, 3, 5, 1]의 데이터가 있다고 가정하자.
1
2
3
4
5
6
7
8
9
배열 데이터 : [4, 10, 3, 5, 1]
배열 인덱스 : [0, 1, 2, 3, 4]
// 이진트리 변환시
4 (인덱스 0)
/ \
10 3 (인덱스 1, 2)
/ \
5 1 (인덱스 3, 4)
예를 들어, 10을 기준으로
- 부모 노드 접근시
- 10의 인덱스 = 1
- 부모 노드를 구하는 식:
i-1 / 2-> 1-1/2 = 0
- 왼쪽 자식 노드 접근시
- 10의 인덱스 = 1
- 왼쪽 자식의 인덱스를 구하는 식 :
2*i + 1-> 2*1 +1 = 3
- 오른쪽 자식 노드 접근시
- 10의 인덱스 = 1
- 오른쪽 자식의 인덱스를 구하는 식 :
2*i + 2-> 2*1 +1 = 4
이런식으로 접근하면 된다.
Heapify
위에서는 완전 이진 트리의 형식으로 변환만 한 것이라, 힙의 속성을 만족시키지 못하고 있다. 이럴 때 이제 Heapify 연산을 해보자.
1
2
3
4
5
4 4 10
/ \ / \ / \
10 3 -> 10 3 -> 4 3
/ \ / \ / \
5 1 5 1 5 1
예시에서 최대 힙으로 만드는 과정을 같이 해보자.
- 마지막 부모 노드(=10)와 두 자식 노드를 비교한다. 3 은 자식이 없어 패스 -> 10은 이미 완벽한 상태라 패스 -> 4는 10보다 작으므로, 10이랑 교환
- 부모모다 큰 자식이 있다면 교환한다. 만약, 최소 힙이라면, 부모모다 작은 자식이 있다면 교환한다.
- 루트 노드까지 이 과정을 반복한다.
이렇게 하면, 단 한번만 이 과정을 수행해도 최대값 10이 루트 노드로 올라온다. 주의할 점은 1번의 수행으로 최소값이나 최대값이 루트노드로 올라오는 것이지, 모든 값이 정렬 되는 것이 아니라는 점이다.
힙 정렬
이렇게 구성된 힙에서 최대값이나 최소값인 루트노드의 값을 꺼내게 되고, 꺼내면서 또 Heapify 과정을 반복하게 됨으로써 정렬을 합니다.