[C++ STL] Heap 자료구조

C++의 Heap

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

 

---

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;
}

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

 

make_heap 결과화면

즉, make_heap 이후에 vector는 재배열되는데 이는 아래와 같다

 

make_heap을 정리하자면, vector는 heap architecture로 재구성하며, 가장 우선순위가 높은 값은 Vector의 맨 앞 인덱스에 위치한다

 

+) 추가적으로 임의의 순서를 갖는 array가 주어질 때 heap 구조를 형성하는데 소요되는 시간 복잡도는 O(n)이다

 

 

---

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을 삽입하면 아래와 같은 결과화면이 나타난다

 

v.push_back(10)

 

만약 주석을 지우고 0을 삽입한다면?

아래와 같다~

v.push_back(0)

 

 

---

pop_heap

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

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

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을 수행하면 마지막 인자를 제외하고 재배열하기 때문에 아래와 같은 결과가 보여진다

 

pop_heap의 결과화면

 

---

일단 이정도만 하자..!

나중에 추가적인 내용은 문제 풀다가 생기면 정리하도록 하겠다 빠잉!

아래는 이 내용 출처!!

 

https://leeminju531.tistory.com/20

(C++ STL) priority_queue, make_heap 제대로 이해하기(1)