힙 정렬

정의

완전이진트리를 기본으로 하는 힙 자료구조를 기반으로한 정렬 방식

 

동작 과정

 

1. 정렬할 N개의 원소로 최대 힙 구성

2. 최대 힙의 루트 노드와 마지막 원소 위치 교환

3. 새 루트 노드에 대해 최대 힙 구성

4. 원소 개수만큼 2와 3을 반복 수행

 

 

시간복잡도

• 최선일 경우 O(nlogn), 평균일 때 O(nlogn), 최악일 경우에도 O(nlogn)이다.
• 과정 1로 build heap 과정으로 O(nlogn)의 시간 복잡도를 가진다.
• 과정 2와 3은 최대 힙에서 원소를 하나 삭제한 다음 heapify를 진행하는 것과 같으므로 O(logn)이 걸리고 원소 개수만큼 반복되므로 O(nlogn)이 된다.
• 따라서 O(nlogn) + O(nlogn) = O(nlogn)의 시간복잡도를 가진다.

 

공간복잡도

• 추가적인 메모리가 필요하지 않으므로 O(N)이다.

 

 

코드

• Python

# (최대)힙 구조 만들기
def heapify():
    for i in range(1, N):
        c = i
        while c > 0:
            root = (c - 1) // 2
            if numbers[c] > numbers[root]:
                numbers[c], numbers[root] = numbers[root], numbers[c]
            c = root
    return


# 힙 정렬하기(오름차순)
def heap_sort():
    for i in range(N - 1, -1, -1):  # n
        # 맨 앞과 맨 뒤를 교환! ( 가장 큰 수를 뒤로 보낸다. 그리고 그 가장 큰 수는 FIX!!!! )
        numbers[0], numbers[i] = numbers[i], numbers[0]

        # 힙구조가 이상해졌으므로 다시 힙구조로 바꾼다.  # logn
        root, c = 0, 1
        while c < i:
            c = root * 2 + 1
            if c < i - 1 and numbers[c] < numbers[c + 1]:
                c += 1

            if c < i and numbers[c] > numbers[root]:
                numbers[c], numbers[root] = numbers[root], numbers[c]
            root = c
    return

• Java
• 첫 번째 heapify

일반 배열을 힙으로 구성하는 역할자식노드로부터 부모노드 비교한다.
n/2 - 1부터 0까지 인덱스가 도는 이유는 부모 노드의 인덱스를 기준으로 왼쪽 자식노드 (i2 + 1), 오른쪽 자식 노드(i2 + 2)이기 때문이다.

public void heapSort(int[] array) {
    int n = array.length;
    
    // max heap 초기화
    for (int i = n/2-1; i>=0; i--){
        heapify(array, n, i); // 1
    }
    
    // extract 연산
    for (int i = n-1; i>0; i--) {
        swap(array, 0, i); 
        heapify(array, i, 0); // 2
    }
}

• 두 번째 heapify

요소가 하나 제거된 이후에 다시 최대 힙을 구성하기 위함이다.
루트를 기준으로 진행한다.(extract 연산 처리)

public void heapify(int array[], int n, int i) {
    int p = i;
    int l = i*2 + 1;
    int r = i*2 + 2;
    
    //왼쪽 자식노드
    if (l < n && array[p] < array[l]) {
        p = l;
    }
    //오른쪽 자식노드
    if (r < n && array[p] < array[r]) {
        p = r;
    }
    
    //부모노드 < 자식노드
    if(i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}

다시 최대 힙을 구성할 때까지 부모 노드와 자식 노드를 swap하며 재귀 진행한다.

퀵정렬과 합병정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않다.

 

장점

• 최소힙, 최대힙의 루트 값이기 때문에 구성을 해놓으면 가장 크거나 가장 작은 값을 구할 때 유용하다.
• 최대 K만큼 떨어진 요소들을 정렬할 때 삽입정렬보다 더욱 개선된 효과를 볼 수 있다.
• 추가적인 메모리를 필요하지가 않고 항상 O(nlogn)이라는 시간복잡도를 가진다.

단점

• 다른 정렬 알고리즘에 비해 난이도가 있다.
• 최선의 경우 퀵정렬과 동일하게 O(nlogn)이 나오지만 실제 시간을 측정해보면 퀵정렬보다는 느리다.
• 안정성을 보장받지 못한다
• 불안정 정렬이다.

 

출처:

https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm
https://gyoogle.dev/blog/algorithm/Heap%20Sort.html

https://deok2kim.tistory.com/178