알고리즘

[Algorithm] 히프 정렬

zs1397 2022. 11. 22. 23:44

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