Heap & priority_queue

기술면접을 위해 기초 CS에 대한 복습중이다.
공부한 내용 중 요점이나 나중에 기억해야할 부분을 정리해보려고 한다.
내가 아는 부분은 생략되어 있을 수 있고, 혹여나 틀린 부분이 있을 수도 있으니 이 글을 보고 '다른 사람'이 공부하기에는 도움이 되지 않을 수 있으니 주의!

Heap의 특징

• 최대/최소 원소를 빠르게 찾을 수 있다.
• Maxheap, Minheap이 있다. (큰 값이 맨 앞, 작은 값이 맨 앞)
• 연산
  • 힙 구성 (Heapify): $O(NlogN)$ (N개를 insert하므로)
  • 삽입 (Insert): $O(logN)$ (바이너리 트리 형태이므로)
  • 삭제 (Remove): $O(logN)$ (바이너리 트리 형태이므로)
• 완전 이진트리라서 배열로 접근 가능 (메모리 효율이 높다)
• 응용
  • 정렬: heapsort
  • 우선 순위 큐: priority queue(★)

사용 방법

• 기본적으로 Priority queue가 C++에서 제공되는 heap의 형태이다.
• // queue를 include 해야한다. #include <queue> // 1) 어떤 타입의 데이터를 사용할 건지 // 2) 어떤 컨테이너를 사용할 건지 // 3) 어떤 연산을 이용할 건지 // 여기서 1)의 데이터 타입과 2)의 데이터 타입이 일치해야 한다. // 예를 들어 priority_queue<T, vector<T>, comp> q; priority_queue<int, vector<int>, greater<int>> q;
• greater를 사용하면 작은 수부터 큰 수로 정렬되므로 Minheap형태가 된다. 즉, top은 가장 작은 값이다.
• // 주로 사용하는 함수들 q.top(); q.pop(); q.push(); q.empty();
• 3번째 인자 compare 구조체
• struct comp { // a는 부모 노드, b는 현재 노드 bool operator()(vector<int> a, vector<int> b) { // 부모 노드가 크면 true를 return해서 swap한다. // 이를 반복하면 결국 가장 작은 값이 조상 노드가 되어 오름차순이 된다. /*return a.at(1) > b.at(1);*/ return a[1] > b[1]; } };