Priority Queue & Heap & Tree
Priority Queue
Queue와 유사하지만, Queue와는 다르게 우선순위가 높은 아이템부터 반환한다.
Priority Queue 동작
insert
우선순위 정보와 함께 아이템을 Priority Queue에 저장한다.
delete
Priority Queue에서 우선순위가 높은 아이템을 반환하며 제거한다.
peek
Priority Queue에서 우선순위가 높은 아이템을 반환하지만, 제거하지 않는다.
만약 우선순위가 5,20,10인 경우 delete()의 결과값은 20이다.
Heap
Heap은 주로 이진트리(Binary tree)기반으로 구현된다.
Max Heap
Max Heap : 부모 노드의 키가 자식 노드의 키보다 크거나 같은 트리
Min Heap
Min Heap : 부모 노드의 키가 자식 노드의 키보다 작거나 같은 트리
Heap의 주요 동작
insert
키값을 포함한 노드를 저장한다.
heap은 insert할 경우 상단에서부터 왼쪽으로 값을 채워나간다.
1. insert(17) > 부모노드3의 자식으로 17이 추가된다.
2. 부모노드 3과 17을 비교하여 17이 더 크기때문에 17이 부모노드가 된다.
3. 부모노드가 된 15와 자식노드 17을 비교 후 자리를 스위칭한다.delete
max heap인 경우 노드의 키값이 가장 큰 아이템을 제거하며 반환, min heap인 경우 키값이 가장 작은 노드를 반환하며 제거한다.
heap은 delete할 경우 root node가 제거된다.
즉, max heap일경우 가장 큰 값을 지닌 root node가 제거,
min heap일 경우 가장 작은 값은 지닌 root node가 제거된다.
1. root node인 20이 제거되며, 가장 최하단에 존재하는 node가 제거되면서 2가 root node가된다.
2. root node인 2와 자식 노드인 15와 11일 비교하여 더 큰값을 지닌 15와 스위칭한다.
3. 부모노드인 2는 자식 노드인 12와 3을 비교하여 더 큰값인 12와 스위칭
4. 12자리에 들어가게된 노드2는 자식노드인 7과 스위칭하여 부모노드7에 자식노드 2와 5가 존재한다.peek
delete와 유사하게 우선순위에 맞는 노드의 키값을 반환하지만, 제거하지않는다.
실습예제
정답:
Tree
Tree는 부모-자식 관계의 계층적인 형태를 가진 구조
Binary Tree
Binary Tree : 자식 노드가 최대 2개인 트리(0~2개)
정리
우선순위 큐와 힙의 관계
힙의 키값을 우선순위로 사용한다면 힙은 우선순위 큐의 구현체가 된다.
우선순위 큐는 행위와 동작만을 표현하는 ADT이며, Heap은 우선순위 큐의 동작을 구현하는 DS이다.
즉, 우선순위 큐(ADT)는 주로 이진트리로 구현되어있는 힙(DS)을 이용하여 구현한다.
사용사례
프로세스 스케줄링
싱글코어인 CPU를 사용하여 다양한 프로세스를 동작시키려 할때 process1이 동작 중일때는 process2,3,4가 ready queue에서 대기하고있다.
만약, ready queue가 우선순위 큐의 종류일 경우 우선순위가 높은 process를 process1이 종료된 시점에 수행할 수 있다.
힙 정렬
delete를 활용하여 우선순위가 높은 키를 기준으로 반환할 수 있다.
max heap인 경우 키값이 높은 노드부터 반환되며 내림차순 정렬이 가능하고,
min heap인 경우 키값이 낮은 노드부터 반환되며 오름차순 정렬이 가능하다.
