[Algorithm] 정렬 - Heap Sort (힙 정렬)

[Algorithm] 정렬 - Heap Sort (힙 정렬)

Heap Sort

Heap 자료구조를 이용하여 정렬하는 방식

Best case, Worst case 모두 시간 복잡도가 \(O(nlogn)\) 그러나 대체로 Quick Sort보다 느림

불안정 정렬(unstable sort) 안정 정렬(stable sort) : 비교하는 원소의 값이 같을 때, input 순서대로 정렬

Heap (약식)

최댓/최솟값을 찾는 연산을 빠르게 하기위해 고안된 자료구조

완전 이진트리(Complete Binary Tree)

부모노드의 Key값은 항상 자식노드의 Key값보다 우선순위가 높음

index i에 대해서 왼쪽 자식 노드의 index: \(i * 2 + 1\) 오른쪽 자식 노드의 index: \(i * 2 + 2\) 부모 노드의 index: \(i / 2\)

구조적으로 Tree이지만 배열로 표현가능

동작

Step 1. 배열을 Heap으로 만든다.

부모노드의 Key값은 항상 자식노드의 Key값보다 우선순위가 높다

Step 1-1.

Step 1-2.

Step 1-3.

Step 2. 첫번째 index와 마지막 index를 swap 후 heap size를 1 줄인다.

Step 2-1.

Step 2-2.

Step 2-3.

Step 2-4.

Step 2-5.

Step 2-6.

코드

public class Sort { public void heapSort(int[] arr) { int lastIndex = arr.length - 1; buildHeap(arr, lastIndex); for(int i = lastIndex; i > 0; i--) { swap(arr, 0, i); heapify(arr, 0, i-1); } } public void buildHeap(int[] arr, int lastIndex) { int parent = (lastIndex - 1) / 2; for(int i = parent; i >= 0; i--) { heapify(arr, i, lastIndex); } } public void heapify(int[] arr, int parentIndex, int lastIndex) { int leftChildIndex = parentIndex * 2 + 1; int rightChildIndex = parentIndex * 2 + 2; int largestIndex = parentIndex; if(leftChildIndex > lastIndex) { return; } if(arr[leftChildIndex] > arr[largestIndex]) { largestIndex = leftChildIndex; } if(rightChildIndex < lastIndex && arr[rightChildIndex] > arr[largestIndex]) { largestIndex = rightChildIndex; } if(largestIndex != parentIndex) { swap(arr, largestIndex, parentIndex); heapify(arr, largestIndex, lastIndex); } } public void swap(int[] arr, int index1, int index2) { int temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } }

왜 \(O(nlogn)\)일까?

Heap Sort의 의사코드를 보면 다음과 같다.

HeapSort(arr) { buildHeap(arr) // O(n) // O(nlogn) for( i = heapLastIndex ~ 0 ) { swap(arr, i, heapLastIndex) heapify(arr, 0, i - 1) } }

Build Heap이 \(O(n)\)인 이유

for 구문이 \(O(nlogn)\)인 이유

from http://jino-dev-diary.tistory.com/36 by ccl(A) rewrite - 2021-09-29 20:01:04