[자료구조] 비선형 자료 구조 ③

1. 힙

그래프, 트리 자료구조에 이어 힙에 대해 알아보고자 한다. 힙은 완전 이진 트리 기반의 자료구조이며, 최소힙과 최대힙 2가지 종류가 있다.

※ 완전 이진 트리란?

왼쪽에서부터 채워진 이진 트리. 마지막 레벨을 제외하고는 모든 레벨은 완전히 채워져 있으며(2개의 자식 노드를 가지는 상태), 마지막 레벨의 경우 왼쪽부터 채워져 있다.

1) 힙의 종류

① 최대힙
: 루트 노드에 있는 키는 모든 자식에 있는 키 중에 가장 크도록 한다. 또한 각 노드의 자식 노드와의 관계 또한 이 조건을 만족하도록 한다.

② 최소힙
: 루트 노드에 있는 키는 모든 자식에 있는 키 중에 최솟값이어야한다. 또한 각 노드의 자식 노드와의 관계 또한 이 조건을 만족하도록 한다.

2) 최대힙의 삽입

① 15의 삽입

② 부모노드(8) < 자식노드(15) 이므로 교환

③ 부모노드(14) < 자식노드(15) 이므로 교환

2. 우선순위 큐

우선순위 대기열이라고도 하며, 큐의 우선순위가 높은 요소가 먼저 나가는 자료 구조

1) Queue

#include <queue>
queue<int> q;
q.push(10);
q.push(20);
// 먼저 입력된 데이터(10,front)이 제거됨
int front = q.front();
q.pop();

2) Priority Queue

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

int main() {
	priority_queue<int, vector<int>, less<int>> mx_pq;
	mx_pq.push(5);
	mx_pq.push(2);
	mx_pq.push(8);
	mx_pq.push(9);
	mx_pq.push(1);
	mx_pq.push(14);

	mx_pq.pop();
	mx_pq.pop();
	while (!mx_pq.empty()) {
		cout << mx_pq.top() << " ";
		mx_pq.pop();
	}
	priority_queue<int, vector<int>, greater<int>> mn_pq;
	mn_pq.push(5);
	mn_pq.push(2);
	mn_pq.push(8);
	mn_pq.push(9);
	mn_pq.push(1);
	mn_pq.push(14);

	mn_pq.pop();
	mn_pq.pop();

	while (!mn_pq.empty()) {
		cout << mn_pq.top() << " ";
		mn_pq.pop();
	}

}