Heap이란
힙(Heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)다. 최악의 경우가 생겨도 힙은 완전 이진 트리이므로 항상 O(logN)의 시간에 해결될 수 있도록 해준다.
힙을 이용한다면 최댓값 혹은 최솟값을 O(logN)에 찾을 수 있다. (일반 배열 사용시 O(N))
최대 힙(Max Heap) / 최소 힙(Min Heap)
최대 힙은 완전 이진트리의 root 부분에 최댓값이 항상 존재하게 되고 최소 힙은 완전 이진트리의 root 부분에 최솟값이 항상 존재하게 된다.
- 최대 힙의 특성: 임의의 subtree에서 root 가 되는 노드를 잡으면 항상 subtree에서의 root 노드는 그 subtree에서 최댓값을 유지한다.
- 최소 힙의 특성 : 임의의 subtree에서 root가 되는 노드를 잡으면 항상 subtree에서의 root 노드는 그 subtree에서 최솟값을 유지한다.
- 주의해야 할 점 : '힙의 자식 노드에서 작은 것이 왼쪽, 큰 것이 오른쪽' 이런 것은 존재하지 않는다. ⇒ 즉, 왼쪽 오른쪽에 무슨 노드가 오던간에 해당하는 subtree에서 루트노드보다 큰 (minheap에서는 작은) 값이면 된다.
실제 구현 시, 최소 힙은 최대 힙에서 음수 값으로만 구현해주면 되기 때문에 최대 힙 구현만 알고 있으면 됨.
최대 힙 삽입 과정(push)
- Insert 할 값을 힙의 마지막 위치에 삽입한다.
- 부모 노드와 비교를 해서 Insert 할 값이 더 크다면 swap 해준다.
- 2번 과정을 계속 반복한다.
최대 힙 삭제 과정(pop)
pop 이기 때문에 root 부터 삭제하면 된다고 이해하면 될듯.
- 삭제할 값(root)를 빼낸다.
- 힙에서 마지막에 있는 노드를 root 로 올린다.
- root로 올린 노드와 그 자식들의 노드를 비교해서 swap 해준다.
- 2~3번 과정을 반복한다.
이진 탐색 트리(Binary Search Tree) 와의 차이점
- 힙은
자식 노드가 부모 노드보다 크면 오른쪽으로 삽입, 작으면 왼쪽으로 삽입과 같은 조건이 존재하지 않는다. - 하지만 이진 탐색 트리에서의 노드 별 값 크기 순은
왼쪽 자식 < 부모 < 오른쪽 자식순으로 된다.
보통 일반적으로 Heap 을 사용하기 위해서 C++ 에서는 Priority_queue 를 많이 사용한다.
이 때 코테에서 까먹지 않기 위해서는 일반적으로 선언해야 하는 메소드와 로직은 외우고 있어야 한다.
실제로 많이 쓰는
priority_queue<int , vector<int>, greater<int> > pq;
priority_queue<int , vector<int>, less<int> > pq;
priority_queue<int , vector<int>, compare > pq;
이 3가지 정도는 무조건 외우고 있어야 한다.
◆ 정리
- 우선순위 큐를 구현한 것.
- priority_queue container 는 vector, deque container 와 붙어서 사용 (list 불가능)
- 내부적으로는 <algorithm>에 있는 힙 관련 함수들을 사용하여 구현.
- 내부구조 default 는 vector container 기반으로 설정
- 정렬기준 default는 내림차순(less<>) 기반으로 설정
＃priority_queue container 생성자와 연산자
- 기본 생성자 형식 priority_queue < [Data Type] > [변수이름];ex)
priority_queue<int> pq; - 내부 컨테이너 변경 priority_queue < [Data Type], [Container Type] > [변수이름];ex)
priority_queue<int, deque<int> > pq; - 정렬 기준 변경 priority_queue < [Data Type], [Container Type], [정렬기준] > [변수이름];ex)
priority_queue<int , vector<int>, greater<int> > pq;
＃priority_queue container 멤버 함수
- bool empty() const;→ check whether container is empty.→ 비어 있다는 것은 size가 0 이기도함.→ 비어있으면 true 반환
- size_type size() const;→ return size 원소의 개수를 반환합니다.
- const value_type& top() const;→ access top element 맨 위에있는 원소를 참조 및 반환 합니다.(삭제하는거 아님)
- void push (const value_type& val);→ insert element인자를 삽입합니다. 내부적으로는 push_back 함수를 이용하여 삽입이 됩니다.
- void pop();→ remove top element 맨 위에있는 인자를 삭제합니다.내부적으로는 pop_heap 알고리즘과 pop_back 함수가 이용되어 우선순위 큐 형태를 유지합니다.
priority_queue <T,vector<T>,compare> pq; 사용법!
struct Custom{
int x;
int y;
int value;
Custom(int value): x(0), y(0), value(value) {}
};
// 오름차순 정렬
struct cmp{
bool operator()(Custom t, Custom u){
return t.value > u.value;
}
};
priority_queue <Custom, vector<Custom>, cmp> pq;위의 코드와 같이 구조체를 선언하고, 해당 구조체에 대한 operator 를 선언해주어 사용할 수 있다. 코드를 잘 외우자!
