힙

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)

1. Insert 할 값을 힙의 마지막 위치에 삽입한다.
2. 부모 노드와 비교를 해서 Insert 할 값이 더 크다면 swap 해준다.
3. 2번 과정을 계속 반복한다.

최대 힙 삭제 과정(pop)

pop 이기 때문에 root 부터 삭제하면 된다고 이해하면 될듯.

1. 삭제할 값(root)를 빼낸다.
2. 힙에서 마지막에 있는 노드를 root 로 올린다.
3. root로 올린 노드와 그 자식들의 노드를 비교해서 swap 해준다.
4. 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 를 선언해주어 사용할 수 있다. 코드를 잘 외우자!