[Data Structures] 챕터8. 힙

• 최대 힙(Max Heap)과 Top에서 최대값을 출력한다. 최소 힙(Min Heap) Top에서 최소값을 출력한다.
• 보관된 값은 정렬되어있지 않다.
• 트리 개념을 활용하여 배열로 구현한다.
• 최대값 혹은 최소값을 매 번 꺼낼 때 유리한 자료구조이다.

 

최대 힙(Max Heap)

---

1. 구현원리

• 완전 이진 트리를 항상 유지한다
• Root 값은 항상 최대값이다

 

2. 값 저장하기

1. 따라서 값을 추가할 때 완전 이진 트리를 유지할 수 있는, 왼쪽에서 비어있는 순서대로 값을 대입한다
2. 대입될 노드와 해당 노드의 부모를 비교한다
3. 대입될 노드가 부모보다 크다면 자리를 바꾼다(Root까지 반복진행한다)

• 항상 자식이 부모보다 작다
• Swap이 아닌 Shift를 쓰자(새로 만든 노드는 완전 이진 트리를 만들 수 있는 자리에 넣지 않고 비워두고 비교한다)

두 자식의 값을 비교할 수는 없지만 부모는 자식보다 항상 큰 값을 가지므로 효율적으로 최대 값을 찾을 수 있다.

 

3. 값 꺼내오기

1. Root 노드를 꺼낸 뒤, 완전이진트리 기준 최하위 노드를 Root 노드로 가져와 자식과 비교해나간다.
2. 가져온 노드를 왼쪽 자식 오른쪽 자식과 비교하여 큰 값과 대체한다
3. 대체된 위치에서 1.과 2.를 반복한다

 

구현하기

• 배열 사용, 0번은 비워 둔다
• 완전이진트리이므로 1번 index부터 해당 index의 위치를 파악할 수 있다.
• 부모 노드를 index로 찾을 수 있다(Index / 2 = parent)
• 자식 노드를 index로 찾을 수 있다(Index*2 = left child, Index*2+1 = right child)
• 값을 추가할 때 배열의 맨 마지막에 넣어준다.

 

 

Push

삽입 성능 : O( LogN )

void Push(const T& item)
{
    if (size_ == capacity_)
        Resize(capacity_ * 2);

    // 삽입: 일단 맨 마지막에 삽입한 후에 부모 노드로 올린다.
    size_ += 1;
    int current = size_; // 마지막에 추가가될 위치 (인덱스) // size_ == last index

    // heap_[0] had a trash value
    while (current != 1 && heap_[current/2] < item) // 부모 위치의 값이 추가하려는 값보다 작다면
    {	
        heap_[current] = heap_[current / 2]; // 부모 위치의 값을 자식 위치로 복사해서 내린다.
        current = current / 2;
    }

    heap_[current] = item; // 최종적으로 결정된 위치에 복사
}

 

Pop

삭제 성능 : O( LogN )

void Pop()
{
    assert(!IsEmpty());

    using namespace std;
    cout << "Pop()" << endl;

    heap_[1].~T(); // 소멸자 호출 

    // 삭제: 가장 마지막 값을 루트로 옮긴 후에 내려 보낸다.
    T last_item = heap_[size_]; // 마지막 아이템 복사
    size_--;					// 크기 줄이기

    int current = 1;			// 루트 노드에서 시작
    int child = 2;				// current * 2 (루트의 왼쪽 자식 인덱스)
    while (child <= size_) // 자식이 있는지 확인
    {
        if (child < size_) // right child가 존재하는가?
            // left, right 중에서 더 큰 자식의 인덱스를 찾는다. 
            child = heap_[child] < heap_[child+1]? child+1 : child; 

        // 현재(current) 값이 자식 중 큰 값 보다 크면 더이상 적절한 위치를 찾을 필요가 없다. 루프 중단
        if (heap_[child] <= last_item)
            break;

        // 자식 값을 부모 위치로 복사, 
        heap_[current] = heap_[child];

        // 그 자식 위치로 current 인덱스 변경, child 인덱스도 그 다음 자식 위치로 변경
        current = child;
        child = current * 2;
    }

    heap_[current] = last_item;
}

 

힙정렬

• 힙의 Push와 Pop을 이용하여 정렬할 수 있다.
• 이 때 동일한 값이 왼쪽 자식이나 오른쪽 자식에 들어갈 수 있으므로 들어갔을 때의 순서가 보장되않는다. 따라서 Unstable 정렬이다
• 시간복잡도 : Push/Pop 모두 O(Log N)이므로 N개를 정렬하면 O(N*Log N)이다.
• 공간복잡도 : 배열을 따로 사용할 때 O(N). 힙 배열 내부에서 정렬할 때 O(1)

 

공간복잡도 O(1) 구현하기

https://www.geeksforgeeks.org/heap-sort/

1. 힙에서 꺼낸 가장 큰 값을 배열 마지막 index에 위치한다.
2. 마지막 index를 제외한 값으로 1.을 반복한다.

 

 

우선순위 큐(Priority Queue)

---

우선순위 큐는 힙을 사용하여 구현할 수 있다

#include <iostream>

#include "../shared/MaxHeap.h"

using namespace std;

struct Patient
{
    int severity; // <- 중증도, 정렬할 때의 1차적인 키(key)로 사용됨
    int time;	  // <- 도착시간, 정렬할 때의 2차적인 키(key)로 사용됨, 중증도가 같을 때는 먼저 온 순서
    const char* name;

    // 우선순위 관점에서 봤을 때 a >= b 인지를 반환하는 함수
    friend bool operator >= (const Patient& a, const Patient& b)
    {
        if (a.severity == b.severity) // 우선순위가 같을 때는 시간을 기준으로 다시 판단 (선착순)
            return a.time <= b.time;   // 숫자로써 time이 작은 것이 먼저 왔다는 의미니까 최종 우선순위가 더 높다.
        else
            return a.severity > b.severity; // 우선순위가 큰 쪽 기준
    }

    friend bool operator < (const Patient& a, const Patient& b)
    {
        return !(a >= b); // 앞의 ! 주의 (operator >= 활용) 
    }

    friend bool operator <= (const Patient& a, const Patient& b)
    {
        if (a.severity == b.severity) // 우선순위가 같을 때는 시간을 기준으로 다시 판단 (선착순)
            return a.time >= b.time;   // 숫자로써 time이 작은 것이 먼저 왔다는 의미니까 최종 우선순위가 더 높다.
        else
            return a.severity <= b.severity; // 우선순위가 큰 쪽 기준
    }


    friend std::ostream& operator << (std::ostream& os, const Patient& p)
    {
        // TODO: 필요하면 구현
        return os;
    }
};

int main()
{
    // 응급실
    MaxHeap<Patient> h;

    // 우선순위가 더 높은 환자 먼저 치료
    // 더 중증인 경우(severity가 큰 경우) 우선순위가 높다.
    // 증상의 무거운 정도가 동일하다면(severity가 같다면) 먼저 온 환자 먼저 치료(time이 작은 환자 먼저)

    h.Push({ 1, 0, "Ironman" });   // 중증도 1의 Ironman 시간 0에 도착
    h.Push({ 1, 1, "Nick Fury" }); // 중증도 1의 Nick Fury 시간 1에 도착
    h.Push({ 3, 2, "Hulk" });      // 중증도 3의 Hulk 시간 2에 도착

    cout << h.Top().name << endl;  // 중증도가 높은 Hulk 먼저 치료
    h.Pop();

    cout << h.Top().name << endl;  // 중증도가 동일하지만 먼저 도착한 Ironman
    h.Pop();
    h.Push({ 2, 3, "Blue Beetle" });

    cout << h.Top().name << endl;  // 늦게 도착했지만 중증도가 높은 Blue Beetle
    h.Pop();

    cout << h.Top().name << endl;  // 마지막으로 Nick Fury
    h.Pop();

    /* 출력 예시
    Hulk
    Ironman
    Blue Beetle
    Nick Fury
    */

    return 0;
}

 

Fixed Priority Queue

---

#include <cassert>
#include <iostream>
#include <iomanip>

class FixedPriorityQueue;

struct Node
{
    int item;
    int idx = -1;
    Node* link = nullptr;
    friend std::ostream& operator << (std::ostream& os, const Node& b)
    {
        os << b.item;
        return os;
    }

    friend bool operator < (const Node& a, const Node& b)
    {
        return a.item < b.item;
    }

    friend bool operator >= (const Node& a, const Node& b)
    {
        return a.item >= b.item;
    }

    friend bool operator > (const Node& a, const Node& b)
    {
        return a.item > b.item;
    }

    friend bool operator <= (const Node& a, const Node& b)
    {
        return a.item <= b.item;
    }
};


class Heap
{
public:
    Heap(int cap = 10)
    {
        assert(cap > 0);

        capacity_ = cap;
        size_ = 0;
        heap_ = new Node*[capacity_ + 1];
    }

    void Resize(int new_capacity)
    {
        Node** new_heap = new Node*[new_capacity];
        memcpy(new_heap, heap_, sizeof(Node) * (size_ + 1));
        if (heap_) delete[] heap_;
        heap_ = new_heap;
        capacity_ = new_capacity;
    }

    Node* Top()
    {
        return heap_[1];
    }

    bool IsEmpty()
    {
        return size_ == 0;
    }

    void Print()
    {
        using namespace std;
        cout << "Index: ";
        for (int i = 1; i <= size_; i++)
            cout << setw(3) << i;
        cout << endl;

        cout << "Value: ";
        for (int i = 1; i <= size_; i++)
            cout << setw(3) << *heap_[i];
        cout << endl;

        cout << "idx:   ";
        for (int i = 1; i <= size_; i++)
            cout << setw(3) << heap_[i]->idx;
        cout << endl;

        cout << "addr: ";
        for (int i = 1; i <= size_; i++)
            cout << setw(18) << heap_[i];
        cout << endl;

        cout << "link: ";
        for (int i = 1; i <= size_; i++)
            cout << setw(18) << heap_[i]->link;
        cout << endl << endl;
    }

    void Push(const Node* item)
    {
        if (this->size_ == this->capacity_)
            Resize(this->capacity_ * 2);

        this->size_ += 1;
    }

    void Pop()
    {
        assert(!this->IsEmpty());

        using namespace std;
        cout << "Pop()" << endl;

        this->heap_[1]->~Node();
        delete this->heap_[1];
    }

protected:
    Node** heap_ = nullptr;
    int size_ = 0;
    int capacity_ = 0;

    friend FixedPriorityQueue;
};


class MaxHeap : public Heap
{
public:
    MaxHeap(int capacity=10) : Heap(capacity){}

    void Push(Node* item)
    {
        Heap::Push(item);

        int current = this->size_;

        // heap_[0] had a trash value
        while (current != 1 && *(this->heap_[current / 2]) < *item)
        {
            this->heap_[current] = this->heap_[current / 2];
            this->heap_[current]->idx = current;
            
            current = current / 2;
        }

        this->heap_[current] = item;
        this->heap_[current]->idx = current;
    }

    void Pop()
    {
        Heap::Pop();

        Node *last_item = this->heap_[this->size_];
        this->size_--;

        int current = 1;
        int child = 2;
        while (child <= this->size_)
        {
            // Dereferencing it to compare!!!! else compare address
            if (child < this->size_ && *(this->heap_[child]) < *(this->heap_[child + 1]))
                child =  child + 1;

            if (*(this->heap_[child]) <= *last_item)
                break;

            this->heap_[current] = this->heap_[child];
            this->heap_[current]->idx = current;

            //cout << "Current = " << current << ", child = " << child << endl;
            //Print();

            current = child;
            child = current * 2;
        }

        this->heap_[current] = last_item;
        this->heap_[current]->idx = current;
    }
};


class MinHeap : public Heap
{
public:
    MinHeap(int capacity=10) : Heap(capacity) {}

    void Push(Node* item)
    {
        Heap::Push(item);

        int current = this->size_;

        // heap_[0] had a trash value
        while (current != 1 && *(this->heap_[current / 2]) > *item) 
        {
            this->heap_[current] = this->heap_[current / 2];
            this->heap_[current]->idx = current;

            current = current / 2;
        }

        this->heap_[current] = item;
        this->heap_[current]->idx = current;
    }

    void Pop()
    {
        Heap::Pop();

        Node* last_item = this->heap_[this->size_];
        this->size_--;

        int current = 1;
        int child = 2;
        while (child <= this->size_)
        {
            // Dereferencing it to compare!!!! else compare address
            if (child < this->size_ && *(this->heap_[child]) > *(this->heap_[child + 1]))
                child = child + 1;
            
            if (*last_item  <= *(this->heap_[child]))
                break;

            this->heap_[current] = this->heap_[child];
            this->heap_[current]->idx = current;

            //cout << "Current = " << current << ", child = " << child << endl;
            //Print();

            current = child;
            child = current * 2;

        }

        this->heap_[current] = last_item;
        this->heap_[current]->idx = current;
    }
};


class FixedPriorityQueue
{
public:
    FixedPriorityQueue(int capacity)
    {
        maxHeap_ = MaxHeap(capacity);
        minHeap_ = MinHeap(capacity);
        size_ = capacity;
    }

    void Push(const int& item)
    {
        using namespace std;

        Node *maxNode = new Node{ item };
        Node *minNode = new Node{ item };
        maxNode->link = minNode;
        minNode->link = maxNode;

        if (maxHeap_.size_ == size_)
        {
            // minHeap_.Top()->link is leaf node at maxHeap
            int current = minHeap_.Top()->link->idx;
            minHeap_.Pop();
            minHeap_.Push(minNode);

            // compare maxNode with parent
            while (current != 1 && *(maxHeap_.heap_[current / 2]) < *maxNode)
            {
                maxHeap_.heap_[current] = maxHeap_.heap_[current / 2];
                maxHeap_.heap_[current]->idx = current;

                current = current / 2;
            }

            maxHeap_.heap_[current] = maxNode;
            maxHeap_.heap_[current]->idx = current;
        }
        else
        {
            minHeap_.Push(minNode);
            maxHeap_.Push(maxNode);
        }
    }

    void Print()
    {
        using namespace std;
        cout << "maxHeap" << endl;
        maxHeap_.Print();

        cout << "minHeap" << endl;
        minHeap_.Print();
    }

public:
    MaxHeap maxHeap_;
    MinHeap minHeap_;
    int size_;
};