[Data Structure] 우선순위 큐(PriorityQueue), 힙(Heap)

우선순위 큐

우선순위가 높은 데이터가 먼저 들어오면 먼저나가는(FIFO) 비선형 자료구조

힙이라고하는 자료구조를 사용해서 구현

 

힙

우선순위 큐를 구현하기 위해 고안된 완전 이진 트리

여러 데이터 중 우선순위가 높은 값을 찾기에 용이하다.

힙에 있는 데이터의 배열을 순회했을 때, 정렬된 데이터가 아니다.(Java Iteration X)

 

최소 힙(Min Heap)

우선순위가 낮은 데이터부터 꺼낸다.

 

최소 힙(Min Heap)

우선순위가 높은 데이터부터 꺼낸다.

 

우선순위 큐 != 힙

제일 중요한 것은 우선순위 큐가 힙이랑 동일한 자료구조가 아니라는 것이다. 힙이라는 것을 우선순위 큐를 구현하기 위해서 만든 자료구조라고 볼 수 있다.

 

트리구조인 힙보다 비효율적이겠지만, 배열을 넣을때마다 정렬해서 우선순위가 높고, 낮은 값을 뺄 수 있다.

=> 우선순위 큐를 구현하고 더 효율적으로 작동해서 힙으로 구현하는 것이다.

 

시간복잡도

데이터 삽입	O(logN)
데이터 삭제	O(logN)
우선순위 높은 데이터 접근	O(1)

 

연산

 

삽입 

새로운 노드에 값을 추가하고 현재 노드의 부모 노드의 값과 비교하면서, 값을 바꿔가는 형태로 삽입힌다.

시간복잡도: O(logN)

 

삭제

마지막 노드에 있는 값을 루트 노드에 넣고 마지막 노드를 삭제한다. 자식 노드와 값을 비교하면서 힙을 유지한다.

시간복잡도: O(logN)

 

 

이용사례

CPU 스케쥴링

준비 상태의 프로세스들을 우선순위 큐에 저장하고, CPU는 우선순위가 높은 프로세스를 먼저 선택해 처리

우선순위가 높은 프로세스들만 처리될 수 있어, 우선순위가 낮은 프로세스는 처리가 되지 않는다.

따라서, 기아가 발생하지 않기 위해, Aging이라는 기법을 사용한다.