힙(Heap)정렬
자료구조 '힙(Heap)'
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
- 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조
- 힙의 종류
1) 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
2) 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
* 완전 이진 트리란?
- 완전 이진트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있어야 함
- 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 함
* 우선순위 큐(Priority Queue)란?
- 큐는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조
- 우선순위 큐는 먼저 들어오는 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조
- 우선순위 큐는 배열, 연결리스트, 힙 등의 자료구조를 통해 구현 가능 → '힙'으로 구현하는 것이 가장 효율적
힙 정렬
- 힙 자료구조의 특성을 이용한 정렬
- 배열을 힙 자료구조에 넣은 다음에 원소를 하나씩 빼면,
→ 최소힙일 경우는 작은 값부터 큰 값 순서대로 정렬되어서
→ 최대힙일 경우는 큰 값부터 작은 값 순서대로 정렬되어서 나옴
- 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성
힙 정렬 과정
- 정렬해야 할 N개의 요소들로 최대힙을 구성 → 내림차순 정렬
- 그 다음으로 한 번에 하나씩 요소를(최댓값부터) 힙에서 꺼냄
- 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬 [최대 힙 삭제 과정]
* 내림차순 정렬을 위한 최대 힙의 구현
- 힙(heap)은 1차원 배열로 쉽게 구현될 수 있음
- 정렬해야 할 N개의 요소들을 1차원 배열에 기억한 후, 최대힙 삽입을 통해 차례대로 삽입
* 최대 힙 삽입 과정
- 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입
- 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킴
* 최대 힙 삭제 과정
- 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소(=루트 노드)를 삭제하는 것
- 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
- 힙을 재구성
결론적으로...
힙 정렬이란, 힙(Heap)이라는 자료구조의 성질을 활용하여 정렬을 하는 방법을 의미한다.
먼저 입력되는 배열의 숫자들을 최대힙 또는 최소힙으로 구성시킨 후 (최소힙/최대힙 삽입 과정), 가장 상위 노드부터 출력하여(최소힙/최대힙 삭제 과정) 숫자들을 정렬한다.
힙 정렬 코드
/* 현재 요소의 개수가 heap_size인 힙 h에 item을 삽입한다. */
// 최대 힙(max heap) 삽입 함수
void insert_max_heap(HeapType *h, element item){
int i;
i = ++(h->heap_size); // 힙 크기를 하나 증가
/* 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정 */
// i가 루트 노트(index: 1)이 아니고, 삽입할 item의 값이 i의 부모 노드(index: i/2)보다 크면
while((i != 1) && (item.key > h->heap[i/2].key)){
// i번째 노드와 부모 노드를 교환환다.
h->heap[i] = h->heap[i/2];
// 한 레벨 위로 올라단다.
i /= 2;
}
h->heap[i] = item; // 새로운 노드를 삽입
}// 최대 힙(max heap) 삭제 함수
element delete_max_heap(HeapType *h){
int parent, child;
element item, temp;
item = h->heap[1]; // 루트 노드 값을 반환하기 위해 item에 할당
temp = h->heap[(h->heap_size)--]; // 마지막 노드를 temp에 할당하고 힙 크기를 하나 감소
parent = 1;
child = 2;
while(child <= h->heap_size){
// 현재 노드의 자식 노드 중 더 큰 자식 노드를 찾는다. (루트 노드의 왼쪽 자식 노드(index: 2)부터 비교 시작)
if( (child < h->heap_size) && ((h->heap[child].key) < h->heap[child+1].key) ){
child++;
}
// 더 큰 자식 노드보다 마지막 노드가 크면, while문 중지
if( temp.key >= h->heap[child].key ){
break;
}
// 더 큰 자식 노드보다 마지막 노드가 작으면, 부모 노드와 더 큰 자식 노드를 교환
h->heap[parent] = h->heap[child];
// 한 단계 아래로 이동
parent = child;
child *= 2;
}
// 마지막 노드를 재구성한 위치에 삽입
h->heap[parent] = temp;
// 최댓값(루트 노드 값)을 반환
return item;
}// 우선순위 큐인 힙을 이용한 정렬
void heap_sort(element a[], int n){
int i;
HeapType h;
init(&h);
for(i=0; i<n; i++){
insert_max_heap(&h, a[i]);
}
for(i=(n-1); i>=0; i--){
a[i] = delete_max_heap(&h);
}
}
힙 정렬 시간복잡도
최선, 평균, 최악 모두 O(nlogn)
힙 정렬 장단점
1. 장점
- 시간 복잡도가 좋은편 (최악의 경우에도 시간 복잡도인 O(nlogn)을 보장)
- 힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때
2. 단점
- 데이터들의 상태에 따라 같은 O(nlogn) 시간 복잡도 라도 조금 느림
- 데이터의 순서가 바뀌는 불안정 정렬 알고리즘
※ 참고 - Python은 heapq라는 모듈을 통해 최소힙, 최대힙 쉽게 구현 가능