1. 히프 정렬: 최대 히프를 이용한 정렬 기법
2. 방법:
- 정렬할 원소를 모두 공백 히프에 삽입
- 루트 노드(가장 큰 원소)를 삭제하여 리스트 뒤 삽입
- 삽입된 원소를 제외한 나머지 원소들에 대해 반복 수행
- 시간 복잡도: O(nlogn)
3. HeapSort Algorithm
heapSort(a[])
n <- a.length -1; // n=히프 크기(원소 개수)
// a[0] 사용x, a[1:n]의 원소를 오름차순 정렬
for(i<-n/2; i>=1; i<-i-1) do
heapify(a,i,n); // 배열 a를 히프로 변환, i는 내부 노드
// 배열 a[]를 오름차순 정렬
for(i<-n-1; i>=1; i<-i-1) do{
temp <- a[1]; // a[1]은 제일 큰 원소
a[1] <- a[i+1];
a[i+1] <- temp;
heapify(a, 1, i);
}
4. Heapify Algorithm: a[1:n]을 히프 구조로 변환
heapify(a[], h, m)
// 루트 h제외한 왼쪽 서브트리와 오른쪽 서브트리는 히프, m = 노드의 최대 레벨
for(j<-2*h; j<=m; j<-2*j) do{
if(j<m) then // j는 큰 값이 왼쪽 또는 오른쪽 자식 노드
if(a[j]< a[j+1]) then j <- j+1;
if(a[h]>=a[j]) then exit;
else a[j/2] <- a[j]; // a[j]를 부모노드로 이동
}
a[j/2] <- a[h]; // a[j/2]는 부모노드
'알고리즘' 카테고리의 다른 글
[Algorithm]쉘 정렬, 기수 정렬, 트리 정렬 (0) | 2022.11.25 |
---|---|
[Algorithm] 퀵 정렬 (0) | 2022.11.22 |
[Algorithm] 위상순서, 임계경로 (0) | 2022.11.02 |
[Algorithm] MCSP_최단거리 (0) | 2022.10.26 |
알고리즘 시험공부) 힙 (0) | 2022.10.17 |