완전 이진 트리
- 삽입할 때, 왼쪽부터 차례대로 추가하는 이진 트리
이와 같은 방식으로 최대 값을 하나씩 뽑아가면서 정렬하는 것이 Heap Sort.
private static void heapSort(int[] arr){
int n = arr.length;
for(int i=(n/2)-1; i>=0; i--{
heapify(arr, n, i);
}
for(int i= n-1; i>0; i--){
swap(arr, 0, 1);
heapify(arr, i, 0);
}
}
1번째 heapify
2번째 heapify
private static void heapify(int[] arr, int n, int i){
int p = i; //부모 노드
int l = i * 2 + 1; // 왼쪽 자식 노드
int r = i * 2 + 2; // 오른쪽 자식 노드
//왼쪽 자식 노드와 부모 노드를 비교하며 큰 값을 부모 노드로 올린다.
if(l<n && arr[p] < arr[l]) p=l;
//오른쪽 자식 노드와 부모 노드를 비교하여 큰 값을 부모 노드로 올린다.
if(r<n && arr[p] < arr[r]) p=r;
//부모 노드를 가리키는 p 값이 바뀌면 위치를 교환하고
//heapify()를 호출하여 과정을 반복한다.
if( i != p ){
swap(arr, i, p);
heapify(arr, n, p);
}
}
참고로, PriorityQueue가 힙으로 구성되어있다.😎