Algorithm & Data Structure/Sort
Heap Sort(힙 정렬)
슝슝이입니다
2024. 4. 17. 23:25
반응형
힙정렬에 대해서 힙 정렬은 완전 이진 트리인 힙을 이용한 선택 정렬의 일종입니다. 배열 요소들을 힙 구조로 재배열한 다음, 가장 큰 요소(또는 가장 작은 요소)를 배열의 끝부분으로 이동시키는 과정을 반복하여 전체 배열을 정렬합니다.
현업에서는 어디에서 쓰일 수 있나? 힙 정렬은 데이터 스트림의 지속적인 입력과 동시에 최대값 또는 최소값을 빠르게 액세스해야 할 때 유용합니다. 따라서 실시간 처리 시스템, 운영 체제의 작업 스케줄링, 대용량 데이터의 배치 처리 등에 적합합니다.
힙 정렬 사이클
힙 정렬의 주요 사이클은 다음과 같이 진행됩니다:
- 힙 구성: 입력 배열을 최대 힙(max-heap) 또는 최소 힙(min-heap) 구조로 변환합니다.
- 요소 추출 및 재구성: 힙의 루트(최대값 또는 최소값)를 힙의 마지막 요소와 교환하고, 루트를 제외한 나머지 힙을 재구성합니다.
- 반복: 위 과정을 배열이 정렬될 때까지 반복합니다.
힙 정렬 시간복잡도와 공간복잡도
- 시간 복잡도:
- 모든 경우: 최선, 평균, 최악 모두 𝑂(𝑛log𝑛)입니다.
- 공간 복잡도:
- 메모리 사용량: 𝑂(1) - 힙 정렬은 주어진 배열 내에서 정렬을 수행하므로 추가적인 메모리를 필요로 하지 않습니다.
- 안정성:
- 힙 정렬은 안정적인 정렬 방법이 아닙니다. 같은 값의 요소가 원래의 순서를 유지하지 않을 수 있습니다.
힙 정렬 예시 code (Java, Golang, Python)
Java 코드
public class HeapSort {
public void sort(int arr[]) {
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
}
- 힙 구축: 배열의 절반에서 시작하여 최대 힙을 구성합니다. 이는 부모 노드가 자식 노드보다 크도록 배열을 재배열하는 과정입니다.
- 요소 추출 및 교환: 배열의 끝으로 최대값을 이동하고, 루트 노드(새로운 최대값)를 배열의 끝과 교환한 후, 남은 힙에 대해 다시 최대 힙을 유지합니다.
- 재귀적 힙화: 자식 노드 중 더 큰 값과 교환 후, 변경된 노드 위치에서 다시 힙 조건을 만족하도록 재귀적으로 힙화를 수행합니다.
Golang 코드
package main
import "fmt"
func heapify(arr []int, n, i int) {
largest := i
l := 2*i + 1
r := 2*i + 2
if l < n && arr[l] > arr[largest] {
largest = l
}
if r < n && arr[r] > arr[largest] {
largest = r
}
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}
func heapSort(arr []int) {
n := len(arr)
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
for i := n - 1; i > 0; i-- {
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
}
}
func main() {
arr := []int{12, 11, 13, 5, 6, 7}
heapSort(arr)
fmt.Println("Sorted array is:", arr)
}
- 힙 구축: 배열을 최대 힙으로 구성합니다. 부모 노드는 자식 노드보다 항상 크거나 같아야 합니다.
- 힙에서 요소 추출: 최대 힙의 루트(최대값)를 배열의 마지막 요소와 교환하고, 힙 크기를 줄인 후에 힙을 재구성합니다.
- 효율적인 메모리 사용: Go의 슬라이스를 사용하여 추가 메모리 할당 없이 배열 내에서 작업을 수행합니다.
Python 코드
def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("Sorted array is:", arr)
- 힙 구성: 배열을 반으로 나누고 거기서부터 힙 구조를 만들어갑니다.
- 최대 힙 유지: 배열의 가장 큰 값을 찾아 루트에 배치하고, 힙의 나머지 부분을 재정렬합니다.
- Python의 재귀적 구현: Python의 재귀 함수를 사용하여 간결하고 이해하기 쉽게 힙 정렬을 구현합니다.
힙 정렬의 장단점
장점:
- 시간 복잡도: 모든 경우에 𝑂(𝑛log𝑛)을 제공합니다.
- 추가 메모리 사용이 적음: 인플레이스 정렬 방식으로 추가 배열이 필요 없습니다.
- 효율적인 최대/최소 값 추출: 힙의 특성상 최대값 또는 최소값을 즉각적으로 추출할 수 있습니다.
단점:
- 복잡한 구현: 단순 정렬 알고리즘에 비해 구현이 복잡합니다.
- 비안정 정렬: 동일한 요소의 상대적 순서가 유지되지 않을 수 있습니다.
- 예측 불가능한 성능: 특히 일부 특정 패턴의 데이터에 대해 예측하기 어려운 성능을 보일 수 있습니다.
추가 정보
힙 정렬은 모든 경우에 대해 𝑂(𝑛log𝑛)의 시간 복잡도를 가집니다. 이는 힙 정렬의 기본 동작 방식 때문입니다. 힙 정렬은 두 주요 단계로 구성됩니다:
- 힙 구축(Heap Construction): 이 단계에서는 입력 배열을 최대 힙이나 최소 힙의 형태로 조정합니다. 이 과정은 𝑂(𝑛)의 시간 복잡도를 가질 수 있습니다. 이는 빌드 힙 과정이 선형 시간에 수행될 수 있다는 사실 때문입니다. "빌드 힙" 단계만 본다면, 최선의 경우 𝑂(𝑛)이 맞습니다.
- 힙에서 요소 추출(Sorting by Heap Extraction): 배열의 각 요소를 힙에서 제거하고, 배열의 끝부터 시작하여 적절한 위치에 다시 삽입합니다. 이 과정은 배열의 각 요소에 대해 𝑂(log𝑛)의 시간이 소요되며, 이는 최대 또는 최소 요소를 제거할 때마다 힙의 재조정이 필요하기 때문입니다.
따라서 전체 힙 정렬의 시간 복잡도는 이 두 단계의 조합으로, 최종적으로 𝑂(𝑛log𝑛)이 됩니다. 힙 구성이 𝑂(𝑛)이 가능함에도 불구하고, 전체 정렬 과정에서 요소를 추출하고 힙을 재조정하는 과정이 반복되기 때문에, 이 부분이 전체 복잡도를 𝑂(𝑛log𝑛)으로 만듭니다.
따라서, 힙 정렬은 최선, 평균, 최악의 경우 모두 𝑂(𝑛log𝑛)의 시간 복잡도를 가집니다. 최선의 경우에 𝑂(𝑛)이라는 설명은 힙 구축 과정에만 해당되며, 전체 정렬 프로세스에 대한 복잡도는 아닙니다.
반응형