[c++][자료구조] heap 구현 / STL / Priority Queue 총 정리

Heap 이란?

◎ complete binary tree (parent node는 2개의 child node를 갖는다.)
◎ parent 와 child 간에 항상 대소 관계가 성립
◎ parent node가 child node 보다 항상 크면 max heap, 항상 작으면 min heap
◎ max heap일때는 최상위 node가 가장 크고 , min heap일때는 최상위 node가 가장 작다.

◎ array의 index는 1 부터 사용한다.
◎ child index는 (parent_index)*2 , (parent_index)*2+1
◎ 반대로 parent index는 (child_index) / 2

1. heap 구현

 

Array를 이용하여 Maxheap을 구현해보았다.

 

변수 / 생성자 / 소멸자

private:

    int* heap; // heap container using array
    int capacity = 0; // size of heap
    int full_memory = 0; // heap array에 할당된 메모리

public:

    //heap 생성자
    
    Heap(int capa = 2){
        full_memory = capa;
        heap = (int*)malloc( (capa+1) * sizeof(int));
    };

    //heap 소멸자
    
    ~Heap(){};

 

함수

 

① heap_push

    // data를 heap에 삽입 , 정렬.
    
    void heap_push(int data){
        
        // 삽입 , 메모리가 다 찼다면 재할당.
        
        if(isfull()) reserve(full_memory * 2);
        heap[++capacity] = data;
        
        // 정렬
        
        int child = capacity;
        int parent = child / 2;
        while(child > 1 && heap[child] > heap[parent]){
            swap(heap[child] , heap[parent]);
            child = parent;
            parent = child / 2;
        }
    }

 

② heap_pop

// heap 최상단 노드 pop , 정렬

    void heap_pop(){
        if(capacity==0) return;
        
        // pop
        
        swap(heap[1],heap[capacity]);
        capacity--;

        // 정렬

        int parent = 1;
        int child = parent * 2;

        if(child+1 <= capacity){
            child = (heap[child] < heap[child+1]) ? child+1 : child;
        }

        while(child <= capacity && heap[parent] < heap[child]){
            swap(heap[parent] , heap[child]);

            parent = child;
            child = parent *2;

            if(child+1 <= capacity){
                child = (heap[child] < heap[child+1]) ? child+1 : child;
            }
        }
    }

 

③ isheap

    // heap 구조를 갖췄는지 확인

    bool isheap(){
        for(int i = 1 ; i <= capacity ; ++i){
            if((i*2)+1 <= capacity && heap[(i*2)+1] > heap[i]){
                return false;
            }
            if((i*2) <= capacity && heap[i*2] > heap[i]) return false;
        }

        return true;
    }

④heap_size

 

// heap size 반환

    int heap_size(){
        return capacity;
    }

 

⑤heap_sort

 

//heap sort

    void heap_sort(){
        int temp = capacity;
        while(capacity != 0){
            heap_pop();
        }
        capacity = temp;
    }

 

그 외 함수들 (make_heap / print_heap / isfull / reserve)

 

make_heap

// arr 를 heap array로 변환

    void make_to_heap(int* arr, int arr_size){
        if(arr_size == 0) return;

        for(int i = 0 ; i < arr_size ; ++i){
            heap_push(arr[i]);
        }
    }

 

print_heap

 //heap 출력

    void printHeap(){
        cout << "Heap : ";
        for(int i = 1 ; i <= capacity ; ++i){
            cout << heap[i] << ' ';
        }
        cout << endl;
    }

 

isfull

// heap array의 메모리가 꽉찼는지 확인
    
    bool isfull(){
        return full_memory == capacity;
    }

 

reserve

 void reserve(int capa){
        (int*)realloc(heap, (capa+1) * sizeof(int));
        full_memory = capa;
    }

 

※ realloc에 대해 더 자세히 알고싶다면 아래 글을 참고하자.

2022.02.12 - [c++/문법] - [c / c++] new / malloc / calloc /realloc 총 정리 & 예제

[c / c++] new / malloc / calloc /realloc 총 정리 & 예제

 

 

 

main 에서 사용

int main(int args, char** argv){

    Heap h;
    
    int arr[10] = {3, 5, 7 , 8 , 10, 21, 6, 13, 31, 25};
    int arr_size = sizeof(arr)/ sizeof(arr[0]);
    h.make_to_heap(arr,arr_size);
    h.printHeap();

    h.heap_sort();
    h.printHeap();
}

출력

---

 

2. heap STL

헤더파일

#include <algorithm>

함수

 

① makeheap

 

heap 속성 갖도록 만든다.

시간복잡도 : log(N)

#include <functional> // greater , less


vector<int>v = {1,2,3,4,5,6,7,8,9,10};

make_heap(v.begin() , v.end()); // Maxheap
// make_heap(v.begin() , v.end() , greater<int>()); // Minheap
// make_heap(v.begin() , v.end() , less<int>()); // Maxheap

 

greater , less 함수에 대해 더 알아보고 싶다면 아래를 참고하자

2022.02.10 - [c++/문법] - [C++] Sort 와 Compare 함수 (Greater , less)

[C++] Sort 와 Compare 함수 (Greater , less)

 

② pushheap

 

heap 마지막에 원소를 삽입.

v.push_back(11); // 마지막에 값을 삽입.

push_heap(v.begin() , v.end()); // 삽입된 값을 알맞은 곳에 정렬.

③ popheap

 

maxheap인 경우 가장 큰 값 제거, minheap인 경우 가장 작은 값 제거.

pop_heap(v.begin() , v.end()); // pop할 값을 index 마지막에 위치 시킴.

// 만약 곧 pop될 값을 얻고 싶다면 int i = v.back();

v.pop_back(); // pop

④ sort_heap

 

힙을 정렬 한다.

시간 복잡도 : O(NlogN)

sort_heap(v.begin() , v.end());

⑤ isheap

 

heap이면 true를, 아니면 false를 return.

 

cout << is_heap(v,begin() , v.end()) <<endl;

⑥is_heap_until

heap인 곳은 pass 하고 heap을 충족하지 않는 찾아서 반환한다. (heap이 아닌 첫 번째 원소를 가리키는 iterator 반환)

vector<int> v = {40,30,50,20,10};
auto it = is_heap_until(v.begin() , v.end());
cout << *it << endl; // 50 이 출력

 

---

 

3. Priority Queue

 

◎heap으로 구현됨

◎push된 순서에 상관없이 항상 최대값 or 최소값(Maxheap or minheap)이 가장 먼저 꺼내진다.

 

maxheap 방식으로 priority_queue 선언

priority_queue <int> pq;
// priority_queue <int , vector<int>, less<int>> pq;

minheap 방식으로 priority_queue 선언.

 

priority_queue <int , vector<int>, greater<int>> pq;

함수 사용법은 queue와 동일!

pq.push(2);
pq.push(3);
pq.push(4);
pq.push(1);

cout << pq.top() << endl; // maxheap : 4 , minheap : 1

while(!pq.empty()){
cout << pq.top() << " ";
pq. pop();
}
// maxheap : 3 2 1 , minheap : 2 3 4

 

알고리즘 문제를 풀 때 Priority Queue 와 Pair를 함께 사용하여 푸는 사용하는 경우가 있다.

궁금하다면 아래 글을 참고하자.

 

2022.02.12 - [c++] - [C++] Priority Queue & Pair 사용법

[C++] Priority Queue & Pair 사용법