우선순위 큐와 힙

우선순위 큐(Priority Queue) 와 힙(Heap)

 

우선순위 큐는들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다.

(응급실 - 생명이 위급한(우선순위 높은) 환자가 먼저 응급실에 들어간다)

 

구현방법

 

1. 배열 기반으로 구현

 데이터의 우선순위가 높을 수록 배열으리 앞쪽에 데이터를 위치시킨다.

 단점 

  데이터를 삽입 삭제하는 과정에서 데이터를 한칸씩 뒤로 밀거나 당겨야하는 비효율적인 연산을 수반한다.

  삽입 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위 비교 연산을 진행해야 한다.

 

2. 연결 리스트를 기반으록 구현

 데이터의 우선순위가 높 을 수록 리스트의 앞쪽에 데이터를 위치시킨다.

 배열처럼 데이터 삽입, 삭제 시 이후 모든 데이터를 한칸씩 밀거나 당겨야하는 비효율적인 연산을 수반하지 않는다.

 단점 

  첫번째 노드부터 마지막 노드까지 우선순위 비교 연산을 진해해야 한다 (배열 기반과 동일한 단점)

 

이러한 단점 때문에 우선순위 큐는 힙을 이용하여 구현하는 것 일반적인 방법이다.

 

3. 힙을 이용하여 구현

 

힙이란?

 이진 트리 중 완전 이진트리에 속하는 구조이다.

 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다.  = 루트 노드에 저장된 값이 가장 커야 한다.

 (우선순위가 높다는 것을 의미 : 값이 작은 것이 우선순위가 높은 구조일 수도 있다)

 

최대 힙(max heap) : 루트노드로 올라갈수록 저장된 값이 커지는 완전 이진트리

최소 힙(min heap) : 루트노드로 올라갈수록 저장된 값이 작아지는 완전 이진트리

 

 

우선순위 큐는 힙이 어울리므로 이제 힙을 구현하는 방법을 고민해야한다.

 

힙을 구현하는 방법 ( 힙 = 완전 이진 트리 = 배열  or 연결 리스트를 이용하여 트리 구현)

1. 배열

 이진트리 구조를 가지며 이러한 구조를 유지해야 하는 힙은 배열 기반으로 구현하는 것이 적합하다. 

 

2. 연결리스트

 연결 리스트 기반으로 힙을 구현하면 마지막 위치에 추가하는 일이 배열기반 구현보다 더 많은 연산을 필요로 한다.