[자료구조]우선순위 큐, 힙 개념 작동 방식

1. 우선순위 큐 (Priority Queue)

일반적인 큐(Queue)는 스택과 비교되어 선입선출의 규칙을 가지는 자료구조를 의미한다.

큐는 무조건 삽입되는 순서에 따라 나오는 순서가 정해지며, 만약 우선순위가 있는 경우 데이터가 삽입될 때마다 정렬을 새로 해야하므로 매우 비효율적이다.

 

우선순위 큐는 선형적인 구조가 아닌 이진트리의 구조를 사용한다.

따라서 각각의 요소들은 우선순위 값과 데이터로 구성되어 있다.

 

 

2. 이진 힙

우선순위 큐를 구현하기 위해 힙(Heap)을 주로 사용한다.

이진 힙은 완전 이진 트리의 형태를 가져야 하며, 최소힙과 최대힙으로 종류가 나뉘게 된다.

따라서 i번째 노드의 부모노드를 찾으려면 (i-1)/2, 자식노드는 2i+1와 2i+2로 찾을 수 있다.

 

최소힙은 루트노드가 가장 작은 값을 가지며, 모든 부모 노드가 자식노드보다 작거나 같아야 한다.

• 삽입
  새로운 요소가 추가되면 가장 마지막 단말노드로 추가되며
  부모노드와 하나씩 비교하여 추가된 요소보다 작은 값이 나올 때까지 올라가게 된다.
• 삭제
  항상 루트노드가 삭제되며 루트노드의 자식노드들을 비교하여 최소힙의 속성을 유지하도록 조정된다.

 

최대힙의 경우 최소힙과는 정 반대로 동작한다.

 

기본적으로 완전 이진트리의 형태를 갖추고 있기 때문에 삽입이나 삭제연산을 하는 경우 O(logN)의 수행시간을 가지게 된다.

 

 

3. 응용분야

우선순위 큐는 생각보다 많은 분야에서 사용되고 있다.

• 컴퓨터 작업 스케줄링 : 작업들 간의 우선순위를 관리하며 중요한 작업을 우선적으로 처리한다.
• 그래프 알고리즘 : 최소값을 찾아내기 위한 최단 경로 알고리즘등에 주로 사용된다.
• 이벤트 시뮬레이션 : 이벤트 내용과 발생 시간에 따라 처리 순서를 조절하기 위해 우선순위 큐가 사용된다.

 

 

이진트리에 대한 기본적인 내용  ▶  [자료구조]이진트리 개념, 종류, 순회방법, 활용