지금 위 이진 트리(binary tree)구조를 보면 heap구조가 아닌 것을 확인할 수 있다.
①heapify 알고리즘을 통해 힙(heap) 구조로 바꾸어 준다.
※트리 구조를 보면 알 수 있듯이 트리 구조를 이용하는 힙정렬의 시간복잡도가 왜 O(N*logN)인지 알 수 있다. 데이터의 총 갯수는 N개 이고, 힙 구조로 만드는 과정에서 heapify를 적용하려는 노드가 tree의 depth관점에서 logN의 수행 시간을 가지기 때문에 전체 트리를 힙 구조로 만드는 복잡도는 O(N*logN)입니다.
하지만!!! 사실상 모든 데이터를 heapify하지 않아도 되므로 O(N)에 가까운 속도를 낼 수 있다. (이건 더 알아보고 차후 포스팅 해보자!)
After heapify
Heapifying이 된 이후 위 그림처럼 Heap구조로 바뀐다.
②이제, RootNode의 값과 마지막 인덱스에 해당하는 노드 값을 Swap한 후, 스와핑 때문에 깨진 힙 구조를 배열의 사이즈를 1개 줄여서(9와 6을 교체하고 9를 정렬된 요소로 fix!!) 다시 heap구조로 바꾸기 위해 heapifying을 한다.
이 과정이 계속되어 root에 있던 값이 점점 fix되면서 오름차순 정렬이 된다.
package sort;
public class Heap_sort {
private static void heapify(int[] heap, int last) {
// Bottom-up heapify(max heap)
for (int i = 1; i < last; ++i) {
int child = i;
while (child > 0) {
int root = (child-1)/2;
if(heap[root]<heap[child]){
swap(heap,child,root);
}
child = root;
};
}
}
private static void heapSort(int[] heap) {
int size = heap.length;
// convertor: arr to heap
heapify(heap,size);
show(heap);
System.out.println();
// 크기 줄여가며 반복적으로 힙 구성
for (int i = size - 1; i >= 0; --i) {
swap(heap,0,i);
heapify(heap,i);
}
}
public static void main(String[] args) {
int[] heap = {5,2,4,6,1,3};
heapSort(heap); // 힙을 이용해서 정렬하는 메서드
show(heap);
}
private static void swap(int[] data, int v1, int v2) {
int temp = data[v1];
data[v1] = data[v2];
data[v2] = temp;
}
private static void show(int[] heap) {
for (int val : heap) {
System.out.print(val+" ");
}
}
}
※위 소스코드에서는 heapify를 특정한 노드를 기준으로 위쪽으로 점점 올라가는 상향식 구현 방식을 사용하였는데, 하향식 구현 방식도 존재한다.(두 방식 모두 시간 복잡도는 동일)
자료구조를 활용한 알고리즘이라 그런지 재밌다
코테에서는 java의 강점인 api를 사용하는 편이 좋은 것 같다.
우선 순위 큐(Priority Queue) 클래스를 통해서도 구현이 가능하다.
우선 순위 큐도 현재 리스트 내에 우선 순위가 높은 순서대로 원소를 반환하는 자료구조이기 때문이다.
package sort;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
public class Heap_sort {
//우선순위 큐 라이브러리를 이용한 힙 정렬
public static void main(String[] args) {
int[] data = {3, 7, 5, 4, 2, 8};
int size = data.length;
// 낮은 숫자가 우선 순위인 int형 우선순위 큐 선언
Queue<Integer> heap = new PriorityQueue<>();
// 높은 숫자가 우선 순위인 int형 우선순위 큐 선언
// Queue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
// arr to heap
for (int i = 0; i < size; ++i) {
heap.add(data[i]);
}
for (int val : heap) {
System.out.print(val + " ");
}
}
}
