[자료구조] #19 Heap(2)

• MaxHeap Class

class MaxHeap {
private:
    static const int root_index = 1;  // 루트 노드의 인덱스는 1로 설정
    static const int HEAP_SIZE = 200; // 힙의 최대 크기는 200으로 설정
    int nodes[HEAP_SIZE];             // 힙 노드를 저장할 배열
    int size;                         // 현재 힙의 크기

    // 주어진 인덱스의 왼쪽 자식 노드의 인덱스를 반환
    int LEFT(int i) { return i * 2; }

    // 주어진 인덱스의 오른쪽 자식 노드의 인덱스를 반환
    int RIGHT(int i) { return i * 2 + 1; }

    // 주어진 인덱스의 부모 노드의 인덱스를 반환
    int PARENT(int i) { return i / 2; }

public:
    // 생성자: 초기 크기를 0으로 설정
    MaxHeap() : size(0) { }

    // 힙이 비어 있는지 확인
    bool empty() { return this->size == 0; }

    // 힙이 가득 찼는지 확인
    bool full() { return this->size == HEAP_SIZE - 1; }

    // 루트 노드(최대 값)를 반환
    int find() {
        // 힙이 비어 있으면 예외를 발생시킴
        if (empty()) throw "error: heap is empty";
        return nodes[root_index];
    }
};

 

• Insert

public:
    // 새로운 요소를 힙에 삽입
    void insert(int priority) {
        // 힙이 가득 찼다면 예외를 발생시킴
        if (full()) throw "error: heap is full";

        size++;  // 힙의 크기를 1 증가시킴
        int i = size;  // 새 요소의 인덱스를 현재 힙의 크기로 설정
        nodes[i] = priority;  // 새 요소를 힙 배열에 추가
        up_heap(i);  // 힙 속성을 유지하기 위해 새 요소를 위로 올림
    }

private:
    // 새 요소를 위로 올리면서 힙 속성을 유지
    void up_heap(int i) {
        // 현재 노드가 루트 노드가 아니라면
        if (i != root_index) {
            // 현재 노드가 부모 노드보다 크다면
            if (nodes[i] > nodes[PARENT(i)]) {
                // 현재 노드와 부모 노드를 교환
                swap(nodes[i], nodes[PARENT(i)]);
                // 부모 노드로 올라가서 다시 확인
                up_heap(PARENT(i));
            }
        }
    }

 

• remove

public:
    // 루트 노드(최대값)를 제거하고 반환
    int remove() {
        // 힙이 비어 있는지 확인하고, 비어 있다면 예외를 발생시킴
        if (empty()) throw "error: heap is empty";

        int highest = nodes[root_index];  // 루트 노드 값을 저장
        nodes[root_index] = nodes[size--];  // 마지막 노드를 루트로 이동시키고 힙 크기 감소
        down_heap(root_index);  // 힙 속성을 유지하기 위해 루트 노드를 아래로 내림
        return highest;  // 제거된 루트 노드 값을 반환
    }

private:
    // 노드를 아래로 내리면서 힙 속성을 유지
    void down_heap(int i) {
        int left = LEFT(i);  // 왼쪽 자식 노드의 인덱스
        int right = RIGHT(i);  // 오른쪽 자식 노드의 인덱스
        int largest = i;  // 현재 노드의 인덱스

        // 왼쪽 자식 노드가 현재 노드보다 크다면 largest를 왼쪽 자식 노드로 설정
        if (left <= size && nodes[left] > nodes[largest])
            largest = left;

        // 오른쪽 자식 노드가 현재 노드보다 크다면 largest를 오른쪽 자식 노드로 설정
        if (right <= size && nodes[right] > nodes[largest])
            largest = right;

        // 만약 largest가 현재 노드와 다르다면(자식 중 하나가 더 크다면)
        if (largest != i) {
            swap(nodes[i], nodes[largest]);  // 현재 노드와 가장 큰 자식 노드를 교환
            down_heap(largest);  // 교환된 자식 노드를 대상으로 다시 down_heap 호출
        }
    }

 

• Heap의 다른 연산들

 

여기서부터 item은 <key, priority>로 구성된다고 가정하자.

 

• decrease-key

 

Step 1) key를 가지는 노드의 index를 찾는다.

 

Step 2) 해당 노드의 priority를 decrement만큼 감소시킨다.

 

Step 3) 해당 index로부터 down-heap을 한다.

 

 

최악의 경우는 루트 노드를 건드려서 제일 깊은 리프노드까지 이동하는 것이라고 볼수 있다.

 

• increase-key

 

Step 1) key를 가지는 노드의 index를 찾는다.

 

Step 2) 해당 노드의 priority를 increment만큼 더한다.

 

Step 3) 해당 index로부터 up-heap을 한다.

 

아래는 실제 코드로 구현한 예시이다.

class Node {
    friend class MaxHeap; // MaxHeap 클래스에게 private 멤버에 접근할 수 있도록 허용
    int key; // 노드의 식별자
    int priority; // 노드의 우선순위
};

// MaxHeap의 nodes 배열은 Node 객체를 가지는 것으로 변경되었다 가정
// MaxHeap에 std::vector<int> indices가 추가되어 key에 대응되는 index 관리

// key에 해당하는 노드의 우선순위를 decrement만큼 감소시키는 메서드
void MaxHeap::decrease_key(int key, int decrement) {
    int i = indices[key]; // key에 해당하는 노드의 인덱스를 찾음
    nodes[i].priority -= decrement; // 우선순위를 decrement만큼 감소
    down_heap(i); // 변경된 노드를 기준으로 down_heap 연산을 수행하여 heap 속성을 유지
}

// key에 해당하는 노드의 우선순위를 increment만큼 증가시키는 메서드
void MaxHeap::increase_key(int key, int increment) {
    int i = indices[key]; // key에 해당하는 노드의 인덱스를 찾음
    nodes[i].priority += increment; // 우선순위를 increment만큼 증가
    up_heap(i); // 변경된 노드를 기준으로 up_heap 연산을 수행하여 heap 속성을 유지
}

 

• 추가사항

 

둘 다 최악의 경우 O(log n)의 시간 복잡도를 가진다.

(down heap/up-heap)

 

노드가 추가/삭제 되거나 두 노드가 swap 되면 indices[key]도 업데이트된다. 

insert: indices[key] = size;
remove: indices[key] = 0; // dummy

def my swap(i, j):
    std::swap(indices[nodes[i].key]], indices[nodes[j].key]])
    std::swap(nodes[i], nodes[j])

 

• Heap Sort

 

정렬 문제

입력 : n의 크기를 가지는 배열(순서는 섞여있다.)

출력 : 배열의 원소를 특정 순서로 정렬

 

Heap sort : heap을 이용하여 정렬

먼저 정렬해야 할 n개의 요소들을 heap에 삽입한다. O(nlog n) 시간

한번에 하나씩 요소를 heap에서 삭제 후 출력한다. O(nlog n) 시간

void MaxHeap::heapsort(int A[], int n) {
    // 배열 A의 각 요소를 heap에 삽입
    for (int i = 0; i < n; i++)
        insert(A[i]);

    // heap에서 요소를 하나씩 제거하여 배열 A에 저장하면서 정렬
    for (int i = 0; i < n; i++) {
        int key = remove(); // heap에서 최대값을 제거하고 반환
        A[i] = key; // 배열 A에 제거된 값을 저장
    }
}

int main() {
    MaxHeap heap; // MaxHeap 클래스의 인스턴스 생성
    int A[8] = {10, 5, 30, 8, 9, 3, 7, 300}; // 정렬할 배열 선언 및 초기화

    // heap 정렬을 수행하여 배열 A를 정렬
    heap.heapsort(A, 8);

    // 정렬된 배열 A의 요소를 출력
    for (int i = 0; i < 8; i++)
        cout << A[i] << " ";
    cout << endl;

    return 0;
}
// 출력 결과 : 300 30 10 9 8 7 5 3