[정렬] 힙 정렬

힙

힙정렬을 이해하기 전에 힙에 대한 이해가 필요하다.  힙을 이해하기 위해선 다음 포스트를 확인해보자. 

https://ybdeveloper.tistory.com/132

 

힙 정렬이란? 

Max Heap, Min Heap을 구성해 정렬하는 방법이다. 
내림차순 정렬을 위해서는 Max Heap, 오름차순 정렬을 위해서는 Min Heap을 구성하면 된다. 
즉, 데이터들을 Max Heap이나 Min Heap 형태로 유지한 채 루트 노드의 데이터를 뽑아내 정렬을 하는 방식이다. 

 

힙 정렬 구현 (내림차순) 

1. n개의 데이터에 대해 반복한다.  O(n) 
  1-1. 배열에 데이터를 삽입하며 Max-Heap 특성을 만족하도록 조정한다. O(lgn)
2. Max-Heap에 데이터가 존재하지 않을 때 까지 데이터를 뽑아낸다.  O(n)  

 

힙 정렬 JAVA로 구현하기

    public void insert(int n) {
        heap[idx] = n;
        int parent = idx/2;
        int child = idx;
        while(child >= 2 && heap[parent] < heap[child]) {
            SWAP(parent, child);
            child = parent;
            parent = child/2;
        }
        idx++;
    }

    public int delete() {
        int data = heap[1];
        heap[1] = heap[idx--];
        int parent = 1;
        int child = 2;
        while(child <= idx && heap[parent] < heap[child]) {
            SWAP(parent, child);
            parent = child;
            child = heap[heap[parent * 2] < heap[parent * 2 + 1] ? parent * 2 + 1 : parent * 2];
        }
        return data;
    }

    public void SWAP(int idx1, int idx2) {
        int temp = heap[idx1];
        heap[idx1] = heap[idx2];
        heap[idx2] = temp;
    }

위 코드는 Max Heap을 구현한 코드이다. Max Heap은 데이터를 삽입하거나, 삭제해도 특성을 유지하고 최상단 루트 노드에는 가장 큰 값을 가진 노드가 위치하게 된다. 따라서 힙 정렬을 구현하기 위해서는 단순히 힙의 특성을 활용하여 가장 맨 위에 있는 루트 노드의 데이터를 가져와 출력 시켜주기만 하면 정렬된 데이터를 얻을 수 있다. 

 

이를 구현한 코드는 아래와 같다. 

    public void sort() {
        int temp = heapSize;
        for(int i=0; i<temp; i++) {
            System.out.print(delete() + " ");
        }
    }

 

힙정렬의 시간 복잡도 

데이터 삽입 

데이터를 삽입하는 작업은 최악의 경우 모든 Level의 노드에 대해 비교 연산을 진행해야 하므로 O(lgn)이다.  그런데 데이터 삽입 작업을 모든 데이터에 대해 반복하므로 O(n * lgn) 이라고 할 수 있다. 

 

데이터 삭제 

데이터를 삭제하는 작업은 최악, 최선 모두 O(1)의 시간 복잡도를 가지고 있다.  데이터 삭제 작업 또한 모든 데이터에 대해 반복하므로 O(n * 1) 이지만, 데이터가 무한대로 커진다면 O(n)은 O(n * lgn)에 비해 큰 영향을 주지 못하므로 생략이 가능하다.

 

따라서 힙 정렬의 시간 복잡도는 O(n * lgn)이다.