[JAVA/자료구조] 힙 정렬(Heap Sort)

---

평균 수행 시간이 O(logN)인 알고리즘

• 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort)
• 한번 수행될때 마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 사용한다.
• 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요하다.

힙 정렬(Heap Sort)

• 최대 힙 트리나, 최소 힙 트리를 구성해 정렬을 하는 방법
• 내림차순 정렬을 위해서 최대 힙을 구성하고, 오름차순 정렬을 위해서 최소힙을 구성한다.
• 이진 트리를 최대 힙으로 만들기 위해 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어지므로 시간 복잡도는 O(log n)이 걸린다.

 

힙 정렬(Heap Sort) 구현

• n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.
• 최소 힙을 구성한다. 최소 힙이란 부모노드가 자식노드보다 작은 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어갈 수 있다.
• 가장 작은 수(루트에 위치)를 가장 큰 수와 교환한다.
• 두번째와 세번째 과정을 반복한다.

 

힙 정렬(Heap Sort) 결과

Min Heap : [10] [50] [20] [80] [60] [70]   출력 : [10]  출력 : [20]  출력 : [50]  출력 : [60]  출력 : [70]  출력 : [80]