[99클럽 코테 스터디 19일차 TIL] #힙 1

왠지 오랜만에 블로그를 쓰는 것 같네요. 꾸준히 무언가를 한다는 게 확실히 어려운 것 같습니다. 19일 차네요 다시 초심을 잃지 않고 열심히 해보겠습니다. 밀린 것도 다음번에 몰아서 한번 쓰긴 해야 할 거 같아요..

 

문제 설명 

---

 

문제 제목 그대로 최소 힙을 구현해서 문제의 조건대로 출력해 주면 되는 문제입니다.

https://www.acmicpc.net/problem/1927

 

 

 

생각 흐름

---

문제를 읽기 전에, 문제 제목에 쓰여있는 최소 힙을 읽고 잠깐 멘붕이 왔었습니다.

예전에 분명 한번 공부했던 개념 같은데 기억에 없었기 때문이었죠...

 

어쩔 수 없이 힙에 대해서 구글링을 할 수밖에 없었어요.

 

힙은 이진트리의 형태를 가진 자료구조로 최대 힙 (Max heap)과 최소 힙(Min heap)으로 나누어지고 그렇다는 뭐 이런저런 개념들을 찾아보았습니다.

 

생각 외로 개념자체는 받아들이기 어렵지는 않았습니다. C++에서는 priority_queue를 사용해서 구현해 주면 되는데

이 자료구조의 특성이 내림차순으로 즉, 큰 수부터 배열을 저장한다는 특성을 가진다는 것이었죠.

 

문제에서 원하는 최소 힙 (부모의 값이 자식의 값보다 항상 작아야 하는)을 만들기 위해서는 오름차순으로 배열을 만들어야 했어요.

 

그래서 오름차순으로 바꾸어주는 priority_queue 선언문을 찾아 적어주었습니다.

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

 

그 이후는 순조로웠습니다. 가장 상위 요소를 가져오는 방법은 pq.top(), 하나씩 제거하는 방법은 pop() 이였기 때문에 이렇게 마무리하였습니다.

 

#include <bits/stdc++.h>
using namespace std;

int n; // 연산의 개수 n
priority_queue <int, vector<int>, greater<int>> pq; // 작은 순으로 배열되는 큐 q

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i ++) {
		int temp;
		cin >> temp;

		if (temp == 0) {
			if (pq.empty()) {
				cout << 0 << "\n";
			}
			else {
				cout << pq.top() << "\n";
				pq.pop();
			}
		}
		else {
			pq.push(temp);
		}
		
	}
	
	return 0;
}

 

 

공부한 내용 정리

---

힙 개념에 대해 처음 물어보는 문제인 만큼 힙 개념에 대해 자세히 공부해 봐야겠다는 생각을 하였습니다.

 

1. 힙 (heap)

힙(heap)은 이진트리 자료구조입니다.

 

• C++ heap의 헤더파일은 #include <algorithm>에 정의되어 있다.
• C++ STL에서 make_heap은 Heap이라는 Container를 제공해 주는 것이 아니라 사용자의 vector를 인자로 받아 힙 구조로 변환시켜 준다
• 한번 해당 함수를 사용해 힙 구조를 구성하면, 새로운 데이터의 삽입과 삭제를 위해 push_heap, pop_heap을 동반해서 사용해야 빠르다.
• C++ Heap의 시간 복잡도는 O(log N)이다. 

 

2. make_heap

vector를 make_heap을 통해 힙을 구성하면, 우선순위가 가장 높은 데이터는 첫 번째 index에 위치하게 된다.

그리고 나머지 요소는 heap에 맞는 구조를 띄게 된다.

 

make_heap은 데이터의 우선순위를 재정의해주지 않으면 기본적으로 max_heap을 구성한다.

 

#include <iostream>      
#include <vector>         
#include <algorithm>

using namespace std;

void print(vector<int>& vs)
{
	for (auto v : vs)
		cout << v << ' ';
	cout << endl;
}

int main() {
	vector<int> v( vector<int> {1,6,5,2,3,8,4,9,7 });
	cout << "Before make_heap V \n";
	print(v);
	cout<<'\n';

	cout << "After make_heap V \n";
	make_heap(v.begin(), v.end());
	print(v);

	return 0;
}

 

위처럼 구현하면 최대 힙이 생성되고 결과화면은 아래와 같다.

 

 

 

3. push_heap

make_heap을 통해 heap 구조를 갖는 Vector에 데이터 삽입을 원할 때 사용한다.

(참고로 vector에 데이터를 삽입할 때는 앞부분을 삽입하면 O(N), 뒷부분에 삽입하면 O(1)의 시간복잡도를 가진다)

 

vector로 make_heap을 형성한 경우, push_heap은 vector의 데이터 삽입 이후에 사용되어야만 한다.

 

 

#include <iostream>       // std::cout
#include <vector>         // std::vector
#include <algorithm>

using namespace std;

void print(vector<int>& vs)
{
	for (auto v : vs)
		cout << v << ' ';
	cout << endl;
}

int main() {
	vector<int> v( vector<int> {1,6,5,2,3,8,4,9,7 });

	make_heap(v.begin(), v.end());
	v.push_back(10);
	//v.push_back(0);
	push_heap(v.begin(),v.end());
	print(v);

	return 0;
}

 

이렇게 10을 삽입하면 아래와 같은 결과화면이 나타난다.

 

 

 

 

4. pop_heap

힙의 삭제 연산은 pop_heap을 통해 하면 된다.

삭제 연산의 시간 복잡도는 O(log N) 이 소요된다.

pop_heap의 우선순위가 가장 높은 값을 vector의 마지막 인자로 위치시키고 Heap Architecture를 재배열한다.

이때, 맨 마지막 인자는 힙 아키텍처에 포함시키지 않은 상태의 재배열을 수행한다.

 

#include <iostream>       // std::cout
#include <vector>         // std::vector
#include <algorithm>

using namespace std;

void print(vector<int>& vs)
{
	for (auto v : vs)
		cout << v << ' ';
	cout << endl;
}

int main() {
	vector<int> v( vector<int> {1,6,5,2,3,8,4,9,7 });

	make_heap(v.begin(), v.end());
	cout << "before pop :";
	print(v);

	pop_heap(v.begin(),v.end());
	
	cout << "after pop :";
	print(v);

	v.pop_back();
	return 0;
}

 

pop_heap을 수행하면 마지막 인자를 제외하고 재배열하기 때문에 아래와 같은 결과가 보인다

 

 

 

이건 솔직히 이해가 살짝궁 안돼서 다시 한번 찾아봐야겠다.

 

 

그림으로 보는 heap의 이해

 

 - index 0은 최상단 노드임을 의미한다.

 - i 번째 노드의 자식 노드는 i * 2 + 1 번째 노드와 i * 2 + 2 번째 노드가 된다.

 - i 번째 노드의 부모 노드는 (i - 1) / 2 번째 노드가 된다.

 - 부모노드는 항상 자식 노드보다 작거나 같다. / 크거나 같다.

 

 위 사진에서 트리 구조를 살펴보면 부모노드는 자식노드 보다 작은 규칙이 있다.

이러한 구조를 Min Heap이라고 한다. Heap은 두 가지의 경우로 나뉘는데 위 사진과 반대로 부모가 자식보다 항상 큰 규칙을 가지면 Max Heap이 된다.

 

이러한 규칙을 유지하며 원소의 추가/제거 과정을 거치면 루트 노드에 있는 원소 값은 Min Heap에서는 최솟값이, Max Heap에서는 최댓값이 된다. 원소의 추가/제거하는 과정이 O(logN)의 복잡도를 갖고 조회는 O(1)으로 효율적인 구조이다.

 

 push

 위 트리 구조에 원소를 추가해 보자. 예를 들어 4를 추가해 보도록 하겠다.

 

 첫 번째로 트리 구조의 제일 끝부분에 원소를 추가한다.

 이후 heap 규칙에 맞게 원소의 위치를 재설정할 필요가 있다. 4는 부모노드인 6보다 작기 때문에 위치를 서로 바꿔주어야 한다. 이러한 과정을 거치다보면 알맞은 위치를 찾을 수 있다.

 

 pop

  Heap에서 pop을 하게 되면 최상단 노드인 루트 노드가 구조에서 빠지게 된다. 

 

 

 이 후 제일 마지막 index에 해당하는 노드가 그 빈 공간을 채운다.

 

 

 push일 때는 말단에서 시작하여 부모노드와 비교를 했지만, pop의 경우에는 최상단 노드부터 시작해서 자식 노드와 비교해 가며 알맞은 위치를 찾는다. 6의 자식노드는 5과 9이고 이 둘 중 더 작은 값인 5가 6보다 작기 때문에 서로 위치를 바꾼다.

 

 

따라서 위와 같은 구조를 최종적으로 갖는다.

 

 구현하는 과정이 어렵지는 않으니 한 번쯤은 직접 구현해 보는 것이 이해하는데 큰 도움이 된다.

 

 

5. priority_queue (우선순위 큐)

priority_queue <자료형, 구현체, 비교연산자>로 정의

1) 자료형은 int, double 등으로 지정가능

2) 구현체의 기본은 vector <자료형>으로 정의

3) 비교 연산자의 default 값은 less <자료형>으로 내림차순 정렬이고, greater <자료형>을 넣어서 오름차순 정렬로 만들 수 있음

 

 

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

 

또한, pair과 함께 사용하면 인자가 여러 개일 때 정렬도 한 번에 구현 가능하다. pair의 first를 먼저 비교하고 first 값이 같은 경우  second 값을 비교하여 정렬 및 저장되기 때문이다.

 

#include <iostream>
#include <queue>
using namespace std;

int main(){
   priority_queue<pair<int, int>> pq;
   
   pq.push(make_pair(10, 100));
   pq.push(make_pair(1, 50));
   pq.push(make_pair(1, 200));
   pq.push(make_pair(50, 50));
   pq.push(make_pair(-10, 200));
   
   int pq_size = pq.size();
   for(int i = 0; i < pq_size; i++){
      cout << pq.top().first << " " << pq.top().second << "\n";
   }
   return 0;
}

 

 

 

출처: https://i-believe-in-me.tistory.com/52

[C++][STL][자료구조] 힙(Heap), 우선순위 큐(Priority queue) (feat. stack, queue, deque)

https://doorrock.tistory.com/13

[코테를 위한 압축 개념] C++ STL 힙(Heap), 우선순위 큐(Priority queue)

https://yummy0102.tistory.com/218

[C++ STL] Heap 자료구조