Heap 기반 Priority Queue 자료구조 (c++)

" class Heap "

 

1. 변수

- vector<int> v  :  heap에 값을 저장하기 위한 vector가 필요하다.

- int root_idx  :  보통 heap의 root index는 0이 아닌 1이 들어간다. 이를 저장하기 위한 변수이다.

- int heap_size  :  현재 heap에 몇가지 내용이 들어가있는지를 저장한다. 이는 마지막위치 index로 쓰이기도 한다.

- int direction  :  Heap 구조가 MinHeap인지, MaxHeap 인지 구별점이 필요하다. 또한, upHeap 등에서 비교시에도 사용된다.

 

2. 함수

- int size()  :  heap_size를 반환한다.

- int isEmpty()  :  heap_size가 0인지 여부를 반환한다.

- void swap(int idx1, int idx2)  :  upHeap, downHeap에서 자리를 옮길시에 필요한 함수로, 두 위치의 값을 바꾼다.

- int top()  :  v[root_idx] 값을 반환한다.

- void upHeap(int idx)  :  parent 값인 idx/2 값의 위치와 비교를 통해 위로 올라가야 하는 경우 swap을 통해 올라간다.

- void downHeap(int idx)  :  left, right 값을 각각 idx*2, idx*2+1로 구한다음, MinHeap의 경우 둘중 적은값을 기준으로 비교 후 swap을 통해 내려간다.

- int pop()  :  top()과 유사하지만, v[root_idx]의 값을 v[heap_size] 값으로 수정 후 downHeap을 통해 자리를 찾아가는 과정이 필요하다.

- void print()  :  for문을 통해 root_idx 부터 heap_size 까지 v[i]를 출력한다.

 

3. class Heap ADT

class Heap {
private:
    vector<int> v;  //Heap 저장을 위한 vector
    int heap_size;  //현재 개수
    int root_idx;   //상단의 인덱스, 보통 1로 설정한다
    int direction;  //Min, Max의 여부
public:
    Heap(int direction) {//생략 }
    int size() {//생략 }
    int isEmpty() {//생략 }
    int top() {//생략 }
    void swap(int idx1, int idx2) {//생략 }
    void upHeap(int idx) {//생략 }
    void downHeap(int idx) {//생략 }
    void insert(int e) {//생략 }
    int pop() {//생략 }
    void print() {//생략 }
};

 

4. 예시코드

- 참조 코드 : github.com/FreeDeveloper97/Data-Structure-based-cpp/blob/main/6.%20Priority%20Queue/Code_cpp/W10_P1_Priority_Queue.cpp

- 참조 문제 : github.com/FreeDeveloper97/Data-Structure-based-cpp/blob/main/6.%20Priority%20Queue/Exercize_pdf/prob-W10_P1.pdf

//
//  W10_2_MinHeap.cpp
//  INHA CLASS
//
//  Created by Kang Minsang on 2020/12/15.
//  Copyright © 2020 Kang Minsang. All rights reserved.
//

#include <iostream>
#include <vector>
using namespace std;
enum direction {MIN = 1, MAX = -1};

class Heap {
private:
    vector<int> v;
    int heap_size;
    int root_idx;
    int direction;
public:
    Heap(int direction) {
        v.push_back(-1);
        this->heap_size = 0;
        this->root_idx = 1;
        this->direction = direction;
    }

    int size() {
        return heap_size;
    }

    int isEmpty() {
        if(size() == 0) {
            return 1;
        } else {
            return 0;
        }
    }

    int top() {
        if(!isEmpty()) {
            return v[root_idx];
        }
        else {
            return -1;
        }
    }

    void swap(int idx1, int idx2) {
        v[0] = v[idx1];
        v[idx1] = v[idx2];
        v[idx2] = v[0];
    }

    void upHeap(int idx) {
        if(idx == root_idx) {
            return;
        }
        int parent = idx/2;
        if(v[parent]*direction > v[idx]*direction) {
            swap(parent, idx);
            upHeap(parent);
        }
    }

    void downHeap(int idx) {
        int left = idx*2;
        int right = idx*2+1;
        if(right <= heap_size) {
            if(v[left]*direction <= v[right]*direction) {
                if(v[left]*direction < v[idx]*direction) {
                    swap(left, idx);
                    downHeap(left);
                }
            }
            else {
                if(v[right]*direction < v[idx]*direction) {
                    swap(right, idx);
                    downHeap(right);
                }
            }
        }
        else if(left <= heap_size) {
            if(v[left]*direction < v[idx]*direction) {
                swap(left, idx);
                downHeap(left);
            }
        }
    }

    void insert(int e) {
        for(int i=root_idx; i<=heap_size; i++) {
            if(v[i] == e) {
                cout<<-1<<"\n";
                return;
            }
        }
        heap_size++;
        v.push_back(e);
        upHeap(heap_size);
    }

    int pop() {
        if(!isEmpty()) {
            int top = v[root_idx];
            v[root_idx] = v[heap_size];
            heap_size--;
            v.pop_back();
            downHeap(root_idx);
            return top;
        }
        else {
            return -1;
        }
    }

    void print() {
        if(!isEmpty()) {
            for(int i=root_idx; i<=heap_size; i++) {
                cout<<v[i]<<" ";
            }
            cout<<"\n";
        }
        else {
            cout<<-1<<"\n";
        }
    }
};

int main()
{
    Heap heap = Heap(MIN);
    int N;
    cin>>N;
    string q;
    while(N--) {
        cin>>q;
        if(q == "isEmpty") {
            cout<<heap.isEmpty()<<"\n";
        }
        else if(q == "size") {
            cout<<heap.size()<<"\n";
        }
        else if(q == "pop") {
            cout<<heap.pop()<<"\n";
        }
        else if(q == "top") {
            cout<<heap.top()<<"\n";
        }
        else if(q == "insert") {
            int e;
            cin>>e;
            heap.insert(e);
        }
        else if(q == "print") {
            heap.print();
        }
    }
}

 

5. 기타

- vector의 정렬 : 오름차순 (begin()+1 이유는 0번째는 값을 저장하지 않기 때문이다)

void sortting() {
    sort(v.begin()+1, v.end());
}

- vector의 정렬 : 내림차순

void sortting() {
    sort(v.begin()+1, v.end(), greater<int>());
}