[알고리즘] 정렬알고리즘 #6 힙 정렬 (Heap Sort)

📍 힙 정렬 (Heap Sort)

힙 소트는 힙 구조를 이용해 정렬하는 알고리즘이다.

힙 구조란 완전 이진 트리의 일종인 자료구조로 MaxHeap과 MinHeap이 있다. MaxHeap은 루트노드가 가진 값은 자식 노드가 가진 값보다 크거나 같다. MinHeap은 반대로 루트노드가 자식노드보다 작거나 같다. 힙 소트에서는 MaxHeap을 사용한다.

1) 정렬되지 않은 배열을 힙 구조로 바꾼다. (construct heap)
2) 최상위 루트 노드를 뽑아 가장 마지막 원소와 교체한다. (extract)
3) 루트노드부터 마지막 원소 전까지 heap구조로 만든다. (heapify / fixheap)
4) 2)로 돌아가 모든 노드를 추출할 때까지 반복한다.

 

📍 C++ 구현 코드

class Solution {
public:
    void heapify(vector<int>& nums, int root, int size){
        if(size<=root){
            return;
        }
        int left = root*2+1;
        int right = root*2+2;
        int largest = root;
        if(left<size && nums[left]>nums[largest]){
            largest = left;
        }
        if(right<size && nums[right]>nums[largest]){
            largest = right;
        }
        if(largest!=root){
            swap(nums[root],nums[largest]);
            heapify(nums,largest,size);
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();

        for(int i=(n-1)/2;i>=0;i--){
            heapify(nums,i,n);
        }

        for(int i=n-1;i>0;i--){
            swap(nums[0],nums[i]);
            heapify(nums,0,i);
        }
        return nums;
    }
};

https://leetcode.com/problems/sort-an-array/ 에서 위의 코드를 실행시킬 수 있습니다. (주어진 시간 내에 모든 케이스를 통과한다. 하지만 통과된 정답들 중에서도 속도가 빠른 편이다.)

 

📍 코드 동작 원리

sortArray 함수 내 첫 번째 for문이 배열을 MaxHeap 형태로 만드는 부분이다. i=(n-1)/2부터 시작하는데 이는 가장 마지막 부모 노드를 의미한다. 가장 마지막 부모노드를 기준으로 그 아래 자식들까지를 힙 구조를 만든다. 그리고 모든 부모 노드에 대해 이를 반복하여 루트 노드를 기준으로 그 아래 모든 자식들이 힙 구조가 되도록 하면 construct heap이 끝난다.

그리고 그 다음 for문이 루트 노드를 추출하고 다시 heap 상태로 만드는 것이다. 앞서 MaxHeap을 생성했으므로 루트노드가 가장 큰 값을 가지고 있다. 따라서 이를 오름차순 정렬로 바꾸기 위해서는 루트노드를 뽑아서 맨 뒤로 보내주면 된다. 이는 코드에서 마지막 원소와 루트노드의 스왑으로 구현된다. 스왑되었다면 가장 작은 원소가 맨 위로 올라갔으니 MaxHeap 구조가 깨졌다. 따라서 다시 루트부터 Top->Down으로 MaxHeapify를 한다. 1번 인덱스의 노드까지 추출했다면 0번인덱스는 가장 작은 값일 것이므로 이제 오름차순 정렬이 완료되었다. 

참고로 내림차순 정렬을 하고자 한다면 minHeap을 이용하면 될 것이다.

 

📍 시간복잡도(time complexity)

힙 소트의 시간복잡도는 O(nlogn)이다. 

 

📍 Unstable / In-Place

힙 소트는 Unstable한 알고리즘이다. heapify하고 루트노드와 마지막 원소를 swap하고 하는 과정에서 배열의 순서가 불안정해질 수 있다. 그리고 힙 소트는 In-Place 알고리즘이다. heap sort도 재귀호출을 하지만 최대 재귀 깊이는 O(logn)이다. 

 

---