힙 정렬 Heap sort

힙 정렬은 힙 트리를 이용한 정렬 방법이다.

힙 트리는 우선순위 큐를 구현하는 데 사용되는 자료구조로,

힙 정렬에서도 우선순위 큐를 이용하면 간단하게 구현 가능하다.

 

1. 힙 트리 

 최대 힙의 경우, 최대값을 root로 두고 이진 트리를 구성하는 트리 구조.

 부모 노드가 자식 노드의 값보다 무조건 큰 값을 갖는다. 

 최소 힙의 경우, 최대 힙의 경우와 반대이다. 

 

 부모 노드 접근 식 : (n - 1) / 2

 n은 현재 노드의 인덱스 값으로, 힙 트리의 경우 이진 트리의 성질을 갖기 때문에 

 데이터 삽입 시, _heap.size() - 1 부터 시작하여 순차적으로 접근한다. 

 

 left 노드 접근 식 : (n * 2) + 1 

 right 노드 접근 식 : (n * 2) + 2

 데이터 삭제 시, 힙 트리의 경우 root의 노드의 데이터를 pop 하기 때문에

 인덱스 0 의 데이터 값을 추출 후, 트리를 정렬해 준다.

 

우선순위 큐 구현

template <typename T, typename Container = vector<int>, typename Predicate = less<T>>
class Priority_queue
{
public:
    void push_back(const T& value)
    {
        _heap.push_back(value);
        int now = (int)_heap.size() - 1;

        while (now > 0)
        {
            int next = (now - 1) / 2;

            if (_predicate(_heap[now] , _heap[next]))
                break;

            ::swap(_heap[now], _heap[next]);
            now = next;

        }
    }

    void pop()
    {
        _heap[0] = _heap.back();
        _heap.pop_back();

        int now = 0;

        while (true)
        {
            int left = (now * 2) + 1;
            int right = (now * 2) + 2;

            //child node가 존재하지 않는 경우
            if ((int)_heap.size() <= left)
                break;

            int next = now;

            if (_predicate(_heap[next] , _heap[left]))
                next = left;

            //둘 중 승자를 오른쪽 노드와 비교
            if ((int)_heap.size() > right && _predicate(_heap[next], _heap[right]))
                next = right;
            
            //노드의 위치가 변경되지 않은 경우
            if (next == now)
                break;

            ::swap(_heap[now], _heap[next]);
            now = next;
        }

    }


    T& top()
    {
        return _heap[0];
    }

    bool empty()
    {
        return _heap.empty();
    }

private:
    Container _heap;
    Predicate _predicate;
};

 

 

힙 정렬은 우선순위 큐를 통해 구현되는 정렬 기법으로 시간 복잡도는 O(NlogN) 이다.

우선순위 큐 사용을 위해 #include <queue> 헤더를 추가해준다.

 

void HeapSort(vector<int>& v)
{
	priority_queue<int, vector<int>, greater<int>> pq;

	//O(NlogN)
	for (int value : v)
		pq.push(value);

	v.clear();

	//O(NlogN)
	while (pq.empty() == false)
	{
		v.push_back(pq.top());
		pq.pop();
	}
}