힙 정렬(Heap Sort)

"힙 정렬"

     : 힙 트리 구조를 이용하는 정렬 방법

 

• 모든 원소를 기준으로 힙 생성 알고리즘(Heapify Algorithm) 사용
• 내림차순을 위해서는 최대 힙을, 오름차순을 위해서는 최소 힙을 구성

 

• 시간 복잡도 : O(N * logN)
• 항상 O(N * logN)을 보장

 

• 병합 정렬과 퀵 정렬만큼 빠르지만, 더 우위에 있음
• 단순히 속도만 비교하면, 퀵 정렬이 더 빠르기 때문에 일반적으로 많이 사용되지는 않음
• 추가적인 배열이 필요하지 않기 때문에, 메모리 측면에서 몹시 효율적

 

"힙 생성 알고리즘"

     : 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘

 

• 하나의 노드에 대해서 수행
• 하나의 노드를 제외하고는 최대 힙으로 구성되어 있는 상태라고 가정
• 시간 복잡도 : O(logN)

---

 

• "힙(Heap)" : 최소값이나 최대값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리
• "최대 힙" : 부모 노드가 자식 노드보다 큰 힙

 

• "이진 트리" : 모든 노드의 자식 노드가 2개 이하인 노드
• "완전 이진 트리" : 데이터가 루트 노드부터 왼쪽 자식 노드, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진 트리

 

class Sort {
	
	public int[] Heap_Sort(int[] heap) {
		
		for(int i = 1; i < heap.length; i++) { // 힙을 구성
			
			int son = i;
			
			
			do { // 힙 생성 알고리즘
				
				int root = (son - 1) / 2;
				
				
				if(heap[root] < heap[son]) {
					
					int temp= heap[root];
					heap[root] = heap[son];
					heap[son] = temp;
				}
				
				
				son = root;
				
			} while (son != 0);
		}
		
		
		
		for (int i = heap.length - 1; i >= 0; i--) { // 크기를 줄여가며 반복적으로 힙을 구성
			
			int temp = heap[0];
			heap[0] = heap[i];
			heap[i] = temp;
			
			
			int root = 0;
			int son = 1;
			
			
			do { 
				son = 2 * root + 1;
				
				
				if(son < i - 1 && heap[son] < heap[son + 1]) // 자식 중에 더 큰 값을 찾기
					c++;
				
				
				if(son < i && heap[root] < heap[son]) { // 루트보다 자식이 크면 교환
					temp = heap[root];
					heap[root] = heap[son];
					heap[son] = temp;
				}
				
				
				root = son;
				
			} while (son < i);
		}
	}
}