힙 정렬 Heap Sort

힙의 형태

완전 이진 트리 : 각 노드의 자식 수가 2 이하이며, Root 노드부터 Leaf 노드까지 빠짐없이 채워져있는 트리

 

최대힙 Max-Heap

부모 노드 > 자식 노드
Root 노트의 값이 가장 크다.

 

최소힙 Min-Heap

부모 노드 < 자식 노드
Root 노드의 값이 가장 작다.

 

힙 배열 저장 방식

Root 노드는 배열의 첫 번째에 저장
각 노드들은 레벨 별로 저장
   ▶ 부모 : 현재위치 / 2
   ▶ 왼쪽 자식 : 현재위치*2
   ▶ 오른쪽 자식 : 현재위치 *2+1

 

힙 배열 저장 방식

 

힙의 높이 

O(logN)

 

힙 특성관리 Max-Heapify

노드가 입력으로 주어졌을 때 max-heap 특성이 유지되도록 바꾸는 연산
입력값이 흘러내리게 함.

 

시간복잡도

O(logN)

Max-Heapify

힙 구조 만들기

입력받은 트리에 Max-Heapify를 반복 적용
Max-Heapify를 최대 O(n)번 호출
시간복잡도

O(NlogN)

 

최대값 추출

Heap에서 가장 큰 값을 제거하고 Max-Heap 구조를 복원하는 연산
① 루트노드 제거
② 리프노드를 루트 노드 위치로 이동
③ Max-Heapify 실행

 

 

힙 소트

① Max-Heap 구조 생성 : O(NlogN)
② 최대값 추출을 n번 반복 : O(NlogN)
③ 전체 수행시간 O(NlogN)

 

구현 JAVA

package test;

import java.util.Arrays;

public class HeapSort {

	
	public static void main(String[] args) {
		
		HeapSort f = new HeapSort();
		
		int[] arr = new int[] {1,4,5,2,7,9,6,8,3};
		
		/****************************
		 * Max Heap 구조로 만들기 
		 * 	① 부모노드가 자식노드보다 큰 형태
		 * 	② 배열 사이즈/2 지점부터 시작한다. (리프노드를 제외) 	
		 ***************************/
		for(int i = arr.length/2; i >= 0; i--) {
			f.maxHeapify(arr, arr.length, i);
		}
		
		/****************************
		 * 힙 정렬하기(최대값 추출)
		 * 	① 루트노드 제거 후 맨 끝 리프노드를 루트노드 위치로 이동
		 * 	② 루트노드부터 MaxHeapify 수행 
		 ***************************/
		for(int i = arr.length-1; i >= 0; i--) {
			
			int tmp = arr[0];
			arr[0] = arr[i];
			arr[i] = tmp;
			
			f.maxHeapify(arr, i, 0);
		}
		
		System.out.println(Arrays.toString(arr));
		
	}
	/**
	 * 최대힙 속성 유지
	 * @param arr
	 * @param size	배열 길이
	 * @param n		현재 위치
	 */
	public void maxHeapify(int[] arr, int size, int n) {
	
		int parent = n;			//부모노드
		int leftChild = n*2+1;	//왼쪽	 자식 노드
		int rightChild = n*2+2;	//오른쪽 자식 노드
		
		/****************************
		 *왼쪽자식노드 확인
		 *	①왼쪽자식노드가 인덱스의 범위 안
		 *	②왼쪽자식노드가 부모노드 보다 큰 경우
		 *	③ 1,2를 만족하면 왼쪽 자식노드를 부모노드와 Switch 
		 ****************************/
		if(size > leftChild && arr[parent] < arr[leftChild]) {
			parent = leftChild;
		}
		/****************************
		 *오른쪽자식노드 확인
		 *	①오른쪽자식노드가 인덱스의 범위 안
		 *	②오른쪽자식노드가 부모노드 보다 큰 경우
		 *	③ 1,2를 만족하면 오른쪽 자식노드를 부모노드와 Switch 
		 ****************************/
		if(size > rightChild && arr[parent] < arr[rightChild]) {
			parent = rightChild;
		}
		/****************************
		 * 부모노드와 자식노드가 바뀌었으면 배열에 변경내용을 저장
		 * 	①n과 parent위치의 값을 바꾸기
		 * 		n = 초기 부모노드, parent = 바뀐 부모노드 
		 * 	②낮은 레벨에도 maxHeapify 적용
		 ***************************/
		if(parent != n) {
			int tmp = arr[n];
			arr[n] = arr[parent];
			arr[parent] = tmp;
			
			maxHeapify(arr, size, parent);
			
		}
		
	}
		
}

 

출처

• 컴퓨터 알고리즘 기초 6강 힙정렬(Heap Sort)(1), T아카데미
• 컴퓨터 알고리즘 기초 6강 힙정렬(Heap Sort)(2), T아카데미