힙 구조, 우선순위 큐

 

 

다익스트라 알고리즘을 공부하다가

학교에선 안 배웠던 우선순위 큐를 사용하여 성능 개선을 한 경우를 많이 사용하길래

저번 학기에 배웠던 힙 구조를 복습해보았다.

 

 

힙 구조란?

 

 

힙은 트리 구조에서의

완전 이진 트리로 부모 노드의 자식이 최대 2개가 가능하며

 

모든 노드가 2개의 자식을 가지고 있다면 포화 이진 트리

 

1개의 자식을 가진 부모 노드나 같은 레벨에 자식이 없는 노드가 존재한다면

완전 이진 트리라고 한다.

 

힙이 되기 위한 조건은 

 

1. 완전 이진 트리

2. Heap Property : 모든 노드는 값을 갖고, 부모 노드의 값은 자식 노드의 값보다 크거나 같다.

 

반대로 최소 힙은 가장 작은 노드가 상위에 있는 것이다.

 

c++ 은 STL에 내장되어 있는 priority_queue 를 사용한다.

#include <queue>

priority_queue<int, vector<int>, less<int> > maxHeap;
priority_queue<int, vector<int>, greater<int> > minHeap;

 

삽입은 가장 마지막 원소에 들어가며 부모 노드와 비교해서 삽입된 노드가 크다면 부모노드와 교체한다.

 

삭제는 pop 경우 가장 상위 노드인 레벨 0 노드가 삭제되며 가장 마지막 노드와 교체하고 삭제한다.

가장 상위노드가 된 마지막 노드는 삽입과 반대로 자식노드와 비교해서 교체해서 내려간다.

 

 

우선순위 큐

 

 

우선순위 큐는 위의 힙을 큐 형식으로 배열을 이용하여 구현하는 것이다.

 

큐 : 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조 (FIFO first in first out)

 

스택 : 가장 뒤에 들어온 데이터가 가장 먼저 나가는 구조 (LIFO last in first out)

 

c++에서는 대부분 vector로 사용하기에 

push로 원소를 삽입하고

pop으로 최대 원소를 꺼내고 배열에서 삭제한다.

 

pq.push({2, 3});

pq.pop();

 

//우선순위 큐 - 다익스트라
priority_queue<pair<int, int> > pq; // maxHeap
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > pq; //minHeap

 

 

 

마치며

 

 

코드만 알아도 알고리즘 문제는 충분히 풀 수 있지만, 문제란 자고로 원리를 알고 풀어야 한다.

자료 구조는 알고리즘과 밀접한 연관이 있고,

코드만 아는 것이 아닌 그 원리와 내부 구조가 어떻게 돌아가는지 머리로 이해하며 푸는 것이

더욱 도움이 될 것이며, 고점이 높을 것이다.

틈틈히 자료 구조를 공부하며 문제를 푸는 것을 추천한다.