[C++] Heap

heap이란

• 완전 이진트리 구조의 자료구조로, 왼쪽 부터 채워나간다.
• 최상단 루트노드는 Min힙일 경우 최소값, Max힙일 경우 항상 최대값을 갖는다.
• 부모노드는 자식노드보다 우선순위가 높다.
• 보통 배열을 사용하여 구현된다.

1. make_heap 으로 힙 구조 만들기

• #include<algorithm>이 필요
• make_heap은 vector를 heap 처럼 변환해주는 것이지, 자체로는 컨테이너가 아님!
• 힙으로 변환한 이후에는 우선순위가 가장 높은 노드가 맨 앞에 위치

std::make_heap 

template< class RandomIt, class Compare >
constexpr void make_heap( RandomIt first, RandomIt last, Compare comp );

EX)
//default는 max heap이다
make_heap(v.begin(), v.end()); 

// min heap을 위해선 비교함수를 지정해야 한다.
make_heap(v.begin(), v.end(), greater<>()); 

• first : 힙을 만들 시작 범위를 지정한다.
• last : 힙을 만들 종료 범위를 지정한다.
• comp : 우선순위를 지정하기 위한 비교함수.
  • 비교함수는 bool cmp(const Type1 &a, const Type2 &b); 형태를 갖는다.
  • 이때 a는 부모노드, b는 자식노드이며, 우선순위가 높으려면 operator<에서 false를 반환해야 한다!
• make_heap은 O(N) 의 시간복잡도를 갖는다.

삽입. push_heap

push_back으로 노드 삽입 -> push_heap 으로 정렬

push_heap은 우선순위에 맞게 힙 구조를 재정렬만 하는 함수다. 즉 vector에 노드를 삽입하는 것은 push_back 등을 이용해 따로 추가한 후 push_heap을 사용해야 한다!!

삽입의 시간복잡도는 O(logN) 이다

std:: push_heap
template< class RandomIt, class Compare >
constexpr void push_heap( RandomIt first, RandomIt last, Compare comp );

EX)
//make_heap을 했던 방식과 동일하다! 
push_heap(v.begin(), v.end()); 
push_heap(v.begin(), v.end(), greater<>()); 

삭제. pop_heap

pop_heap으로 정렬 -> pop_back으로 노드 제거

pop_heap은 루트에 있던 노드를 컨테이너의 맨 뒤로 보내기만 하는 함수다. 즉 맨 뒤로 보내진 최우선순위 노드를 vector에서 pop_back등을 이용해 따로 삭제해주어야 한다.

삭제의 시간복잡도는 O(logN) 이다

std:: pop_heap
template< class RandomIt, class Compare >
constexpr void pop_heap( RandomIt first, RandomIt last, Compare comp );

EX)
//make_heap을 했던 방식과 동일하다! 
pop_heap(v.begin(), v.end()); 
pop_heap(v.begin(), v.end(), greater<>()); 

---

2. 힙으로 구현된 우선순위 큐를 사용하기

• #include <queue>가 필요
• 힙으로 구현이 되어있기 때문에 힙으로 풀어야 하는 문제에서 편리하다
• 지정된 우선순위에 따라 우선순위가 가장 높은 값이 Top에 위치하게 된다

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

EX)
//기본적인 우선순위큐 선언
priority_queue<int> q;

//내림차순으로 이루어진 우선순위큐 선언
priority_queue<int, vector<int>, greater<int>> minq;

//선언과 초기화를 동시에 하는 방식. iterater로 바로 복사 가능
priority_queue<int> q(v.begin(), v.end());

• T : 컨테이너에 담을 자료형
• Container : vector<T>의 꼴로 적는다. 내부적으로 vector로 구현되는듯

• Compare : 우선순위를 지정할 비교함수, default는 less여서 Max heap이다

• T 에 연산자 오버로딩을 통해 operater<를 정의한다면, 원하는 우선순위를 지정해줄 수 있다!!

Priority_Queue의 주요 메소드

멤버	설명
.top()	우선순위가 가장 높은 노드를 반환
.push()	우선순위에 맞게 노드를 추가
.pop()	우선순위가 가장 높은 노드를 제거
.empty()	큐가 비어있다면 true, 아니라면 false
.size()	큐에 존재하는 원소의 갯수

(포스트번호: cpp_heap)

TOP