[자료구조] 힙 정렬

힙-정렬

2022.01.18 - [2022/자료구조 + 알고리즘] - [자료구조] 힙

[자료구조] 힙

앞에서 설명한 바와 같이, 힙으로 우선순위 큐를 구현할 경우 모든 우선순위 큐 ADT의 함수들을 로그 시간 또는 그보다 효율적으로 구현할 수 있는 장점이 있다. 이번에는 우선순위 큐 P를 이용하여 리스트 L을 정렬하는 PriorityQueueSort 정렬 기법을 다시 보자!!

 

첫 번째 단계에서, i번째의 (1 ≤ i ≤ n) insert 연산은 각각 O(1 + log i) 시간이 소요된다(연산이 수행된 후 힙에 i개의 원소가 있기 때문에). 

이와 유사하게 두 번째 단계에서 j번째의 (1 ≤ j ≤ n) removeMin 연산은 각각 O(1 + log(n - j + 1)) 시간이 소요된다(연산이 수행된 후 힙에 n - j + 1개의 원소가 있기 때문에).

=> 각 단계의 실행 시간은 O(nlogn)이 되고, 우선순위를 구현하기 위해 힙을 사용할 경우 전체 우선순위 큐 알고리즘의 실행시간은 O(nlogn)이 된다.

이러한 정렬 알고리즘을 힙-정렬(heap-sort)이라 한다.

힙-정렬 알고리즘은 n개의 원소를 갖는 리스트 L을 O(nlogn) 시간에 정렬한다. 이때, L의 두 원소는 O(1) 시간에 비교 가능하다고 가정한다.

힙-정렬의 인-플레이스(In-place) 구현

정렬된 리스트 L이 배열로 구현되어 있다면, 힙 정렬의 속도를 향상시킬 수 있으며 리스트 L 자체를 이용하여 힙을 저장하여 별도의 힙 자료구조를 사용할 필요가 없다. 다음 알고리즘을 살펴보자!!

1. 역 비교자(reverse comparator)를 사용하여 가장 큰 원소가 힙의 루트에 오도록 한다. 알고리즘을 실행하는 동안, L의 왼쪽 부분(순위(인덱스) i - 1까지)에 힙의 원소들을 저장하고, L의 오른쪽 부분(i부터 n - 1까지)에 시퀀스(배열)의 원소들을 저장한다. 따라서 L의 처음 i개 원소들(0, ..., i - 1)이 힙의 벡터 표현이 된다(노드 번호가 1 대신 0에서 시작). 즉 순위 k에 저장된 원소는 순위 2k+1과 2k+2에 저장된 그 자식들보다 크거나 같다.

   

   L의 왼쪽 부분은 힙 원소 저장, 오른쪽 부분은 시퀀스 원소들 저장

2. 알고리즘의 첫 단계에서, 비어 있는 힙에서 출발하여 힙과 시퀀스의 경계를 한번에 하나씩 왼쪽에서 오른쪽으로 이동한다. 단계 i(i = 1, ..., n)에서, 순위 i-1에 있는 원소를 힙에 추가한다. 위에 그림 (a)를 보면 1단계로 순위(인덱스) 0에 있는 value가 3인 원소를 힙에 추가하였다.
3. 알고리즘의 두 번째 단계에서, 비어있는 시퀀스에서 출발하여 힙과 시퀀스의 경계를 한 번에 하나씩 오른쪽에서 왼쪽으로 이동한다. 단계 i(i = 1, ..., n)에서, 우리는 힙에서 최대값을 제거하여 순위 n - i에 저장한다. 아래 그림의 (,e)를 보면 시퀀스의 모든 원소를 힙으로 이동시켜서 시퀀스가 비어있다. 그래서 (f)에서 힙의 최댓값 7을 제거하고 처음 시퀀스로 옮기는 것이기 때문에 첫 단계니까 이 7을 5 - 1인 4번째 인덱스에 저장하였다. 나머지도 차례대로 진행한다. 

(a)부터 (e)까지 원소들을 힙에 추가, (f)부터 (j)까지 연속적으로 원소를 삭제하여 시퀀스에 추가

리스트 자체 외에는 일정한 양의 공간만 추가로 필요하기 때문에, 위와 같은 힙-정렬의 변형을 인-플레이스(in-place)라 한다. 즉, 원소들을 시퀀스의 밖으로 옮기거나 다시 들여오는 대신, 시퀀스 내부에서 움직인다. 일반적으로 정렬되는 객체 자신이 필요한 메모리 외에 일정한 양의 공간만 추가로 사용할 경우, 이러한 정렬 알고리즘을 인-플레이스라고 한다.

 

상향식(Bottom-Up) 힙 생성

힙-정렬 알고리즘의 분석을 통하여 n개의 키-원소 쌍을 저장하는 힙을 O(nlogn) 시간에 생성할 수 있음을 알았다!! 즉, n번의 연속적인 insert를 통하여 생성된다. 다음에 생성된 힙을 사용하여 순서대로 원소를 삭제한다. 하지만 힙에 저장된 모든 키가 사전에 주어진다면, O(n)시간에 실행되는 상향식 생성 방법을 사용할 수 있다.

n이 2^1 -1개 주어졌다고 가정하자(위 사진 참고). 즉, 사진의 첫 번째 힙은 모든 레벨이 꽉 찬 완전 이진트리이고, 따라서 힙의 높이 h = log(n + 1)이다. 비재귀적인 방법으로 설명하면, 상향식 힙 생성은 다음과 같은 h = log(n + 1) 단계로 이루어진다.

1. 첫 번째 단계에서(위 그림의 (a) 참고), 각각 하나의 엔트리를 갖는 (n + 1)/2개의 기본 힙들을 생성한다.
2. 두 번째 단계에서(위 그림 (b)-(c)), 기본 힙들을 두 개씩 합치고 새로운 엔트리를 하나씩 추가하여 각각 세 개의 엔트리를 갖는 (n + 1)/4개의 힙을 구성한다. 새로운 키는 처음에는 루트에 놓이지만 힙-순서 특성을 만족하기 위해 자식과 교환될 수 있다.
3. 세 번째 단계에서(위 그림 (d)-(e)), 두 개씩의 3-엔트리 힙(전 단계에서 만들어진)을 합치고 새로운 엔트리를 하나 추가하여 각각 일곱 개의 엔트리를 갖는 (n + 1)/8개의 힙을 구성한다. 새로운 키는 처음에 루트에 놓이지만 힙-순서 특성을 만족하기 위해 다운-힙 버블링을 통해 아래로 움직일 수 있다.
4. 2 ≤ i ≤ h인 i번째 단계에서, 두 개씩의 2^(i-1) - 1 엔트리를 갖는 힙(전 단계에서 만들어진)을 합치고 새로운 엔트리를 추가하여 각각 2^1 - 1개의 엔트리를 갖는 (n + 1)/2^i 힙을 생성한다. 새로운 엔트리는 처음에 루트에 놓이지만 힙-순서 특성을 만족하기 위해 다운-힙 버블링을 통해 아래로 움직일 수 있다.
5. 마지막 단계에서(위 그림 (f)-(g)), 두 개의 (n - 1)/2 엔트리를 갖는 힙(전 단계에서 만들어진)을 합치고 새로운 엔트리를 하나 추가하여 n개의 엔트리를 갖는 최종 힙을 생성한다. 새로운 엔트리는 처음에는 루트에 놓이지만 힙-순서 특성을 만족하기 위해 다운-힙 버블링을 통해 아래로 움직일 수 있다.

재귀적 상향식 힙 생성

이 알고리즘은 힙으로 만들려는 키들을 포함한 시퀀스를 매개변수로 하여 재귀적으로 호출한다.

Algorithm BottomUpHeap(L):
    input: n = 2^(h+1)-1개의 엔트리를 저장하는 STL 리스트 L
    output: L의 엔트리를 저장하는 힙 T
    if L.empty() then
    	return an empty heap
    e <- L.front()
    L.pop_front()
    Split L into two lists, L1 and L2, each of size (n - 1)/2
    T1 <- BottomUpHeap(L1)
    T2 <- BottomUpHeap(L2)
    Create binary tree T with root r storing e, left subtree T1, and right subtree T2
    Perform a down-heap bubbling from the root r of T, if necessary
    return T

어따 써야할지 몰라서 그냥 여기 추가!!

우선순위 큐에서 removeMin 함수를 사용하면 가장 작은 키를 엔트리를 삭제한다. 그런데 가장 작은 키 말고도 임의의 엔트리를 삭제해야 할 필요가 있다!! 따라서 새 연산이 필요하다.

복수의 같은 키들이 있을 수 있기 때문에 엔트리를 삭제하기 위해 키 값을 사용할 수는 없다. 대신 우선순위 큐 연산 insert(e)가 확장되어 원소 e를 삽입한 후 새롭게 생성된 엔트리의 레퍼런스 즉 위치(position)를 반환한다고 가정하자. 이 위치가 엔트리에 영구히 부착되어 만약 엔트리의 순서가 내부에서 변경되더라도 이 위치는 이 엔트리에 고정되어 있다. 따라서 위치는 각 연산이 적용되는 엔트리를 유일하게 식별할 수 있는 방법을 제공한다.

다음과 같은 추가적인 연산을 지원하는 우선순위 큐 P를 정의하자!!

• insert(e): 원소 e를 P에 삽입한 후 그 엔트리를 가리키는 위치를 반환
• remove(p): P로부터 p가 가리키는 엔트리를 삭제
• replace(p, e): p가 가리키는 엔트리에 연관된 원소를 e로 교체하고 수정된 엔트리의 위치를 반환

template <typename E, typename C>
class AdaptPriorityQueue {		// 적응 가능한 우선순위 큐
protected:
    typedef std::list<E> ElementList;	// 원소들의 리스트
public:
    int size() const;			// 원소의 개수
    bool empty() const;			// 큐가 비었나
    const E& min() const;		// 최소 원소
    Position insert(const E& e) {	// 원소 삽입
    	typename ElementList::iterator p = L.begin();
        while (p != L.end() && !isLess(e, *p)) ++p;	// 더 큰 원소를 탐색
        L.insert(p, e);			// p 앞에 삽입
        Position pos;			// 삽입된 위치
        pos.q = --p;		
        return pos;
    }
    void removeMin();			// 최소 원소 삭제
    void remove(const Position& p) {	// 위치 p의 원소 삭제
    	L.erase(p.q);			// 포지션 p 삭제
    }
    Position replace(const Position& p, const E& e) {	// 위치 p의 원소 교체
    	L.erace(p.q);			// 기존 엔트리 제거
        return insert(e);		// 새 엔트리 삽입
    }
private:
    ElementList L;				// 우선순위 큐 내용
    C isLess;					// less-than 비교자
};

class Position {				// 큐 내의 위치
private:
    typename ElementList::iterator q;	// 리스트 내의 위치
public:
    const E& operator*() { return *q; } // 이 위치에 있는 원소
    friend class AdaptPriorityQueue;	// 접근 허가
};

---

참고 문헌

[1] Michael T. Goodrich, Roberto Tamassia, Davaid M. Mount, C++로 구현하는 자료구조와 알고리즘, WILEY, 2013.