[알고리즘] 힙 정렬(Heap Sort)

 

 

완전 이진트리를 기본으로 하는 힙(Heap) 자료구조 기반 정렬 방식

불안정 정렬

 

완전 이진 트리란? 삽입시 왼쪽부터 차례대로 추가하는 이진트리

 

 

💡 HEAP?

 

완전 이진 트리의 일종. 우선순위 큐를 위해 만들어진 자료구조

MAX, MIN 쉽게 추출할 수 있는 자료구조

 

 

---

 

Heap Sort

Max Heap Tree / Min Heap Tree를 구성해 정렬하는 방법

내림차순 정렬 → Max Heap Tree

오름차순 정렬 → Min Heap Tree

1. 정렬할 n개의 요소들로 최대힙을 만든다 (내림차순)
2. 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장
3. 삭제되는 요소(최댓값)은 값이 감소되는 순서로 정렬됨 최댓값 뽑아내기

 

• 마지막 요소를 루트값으로 대체
• 최대 힙 구성
• 힙의 사이즈가 1보다 크면 위의 과정 반복

 

코드(c++)

void heapSort(int arr[]){
	int n = arr.length;

	//max heap 초기화
	for(int i=n/2-1; i>=0; i--)
		heapify(arr, n, i);  //1

	//최댓값 추출
	for(int i=n-1; i>0; i--){
		swap(arr, 0, i);
		heapify(arr, i, 0);  //2
	}
}

1: max heap 초기화하기 → 자식 노드부터 부모 노드 비교

2: max root가 제거되고 다시 max heap 구성하기 → 루트 기준을 진행

 

void heapify(int arr[], int n, int i){
	int p = i;
	int l = i*2+1;
	int r = i*2+2;

	//left
	if(l<n && arr[p] < arr[l]) p = l;
	//right
	if(r<n && arr[p] < arr[r]) p = r;

	//부모 < 자식
	if(i != p){
		swap(arr, p, i);
		heapify(arr, n, p);
	}
}

 

 

---

 

🤔 언제 사용하면 좋을까?

 

• max, min 값을 구할 때
  • Max Heap or Min Heap 의 루트 값이기 때문에 한 번의 힙 구성을 통해 구하는 것 가능
• 최대 k 만큼 떨어진 요소 정렬할 때
  • Insertion Sort보다 개선된 결과..

 

정렬은 Quick Sort 나 Merge Sort 가 더 성능이 좋다

 

 

시간 복잡도

 

• 힙 트리의 전체 높이가 거의 logn (완전 이진 트리이므로). 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 logn 만큼 소요된다.
• 요소의 개수가 n개 이므로
• → O(nlogn)

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!

 

 

 

 

 

 

참고: https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html