Data Structure in C++ - Heap

본 포스팅 시리즈에서는 모든 프로그래머들이 반드시 알아야 할 가장 기본적인 자료구조를 다룰 예정이다.

앞으로 다룰 내용은 프로그래머에게 기본 소양이며, 본인 스스로 직접 구현할 수 있어야 한다. 

 

| 여섯 번째 순서는 힙이다. 

heap이란 완전 이진트리의 일종으로 부모 노드와 자식 노드 간에 항상 대소 관계가 성립하는 자료구조이다. 
부모의 노드가 자식 노드보다 크다면 Max Heap, 작다면 Min Heap이라고 한다. 이때 부모 노드와 자식 노드 간에 관계만 존재할 뿐 형제 노드 사이에는 아무런 관계가 없다. 
위에서 말한 대소관계 이외에도 따로 우선순위를 위한 정의가 가능하며, 그러한 자료구조를 우선순위 큐라고도 한다. 

힙은 보통 힙정렬 알고리즘, 우선순위 큐의 구현 등에 사용된다. 항상 최솟값 혹은 최댓값이 필요한 시나리오에서 힙은 매우 유용하며 또한 원소 중 가장 n번째 작은 수를 구하거나 하는 자료구조에도 사용이 된다.

보통 힙 에서 삽입, 삭제 연산 등에 시간 복잡도 O(logN)이 소모된다. 

힙은 앞에서 본 자료구조와는 다르게 링크드 리스트가 아닌 배열로 구현하는 편이다. 
아래는 힙을 배열로 구현하기 위한 내용과 구현 사항이다. 

• 완전 이진트리는 배열로 구현한다.
• 보통 특정 노드의 index를 current라 한다면 왼쪽 자식 노드는 current * 2 + 1, 오른쪽 자식 노드는 current * 2 + 2이다. 

template <typename T>
class Heap
{
private:
    vector<T> heap_;
public:
    Heap() {}
    ~Heap() {}
    bool IsEmpty() {
        return this->heap_.size() == 0;
    }
    int size() {
        return this->heap.size();
    }

    T top() {
        if(this->heap_.size() == 0){
            cout << "Heap is empty" << endl;
        }else{
            return this->heap_[0];
        }
    }

    void push(T value){
        this->heap_.push_back(value);

        int current = this->heap_.size() - 1;
        while (current > 0 && this->heap_[current] < this->heap_[(current - 1) / 2])
        {
            swap(this->heap_[current], this->heap_[(current - 1) / 2]);
        }
    }

    void pop(){
        

        this->heap_.pop_back();
        int size = this->heap_.size() - 1;
        this->heap_[0] = this->heap_[size];
        int current = 0;

        while(current * 2 + 1 < size) {
            int child = current;
            if(heap[current * 2 + 1] > heap[current]) {
                child = current * 2 + 1;
            }
            if (current * 2 + 2 < size && heap[(current * 2 + 2)] > heap[child]) {
                child = current * 2 + 2;
            } 

            if ( cuild == current ) break;

            swap(this->heap_[current], this->heap_[child]);

            current = child;
        }   
    }
};