[CS 발표_08] 우선 순위 큐의 동작 원리, 힙의 삽입/삭제

우선순위 큐의 동작원리에 대해 설명해주세요.

우선 순위 큐란?

우선순위 큐 : 우선순위가 높은 데이터부터 꺼내는 자료구조

• 배열, 연결 리스트, 힙으로 구현 가능하나 주로 가장 효율적인 힙을 가지고 구현한다.
• top이 최대면 최대힙, top이 최소면 최소힙으로 표현, 힙으로 구현된 이진 트리는 모든 정점이 자신의 자식 요소보다 우선순위가 높다는 성질을 가지고 있다. 시간 복잡도는 O(logN).

힙이란?

• 완전 이진 트리의 한 종류. (최대 힙 & 최소 힙)
• 최대 힙은 부모 노드가 자식 노드의 값보다 크고 최소 힙은 부모 노드가 자식 노드의 값보다 작다.
• 최대 힙과 최소 힙을 이용해 최댓값과 최솟값을 빠르게 찾을 수 있어 우선순위 큐를 구현하거나 힙 정렬을 하는 데 주로 사용한다.

힙의 삽입/삭제 연산

삽입/삭제 예시 그림은 < 기술 면접 대비 CS 전공 핵심요약집 >을 보고 따라 그린 것입니다.

삽입

힙에 데이터를 삽입할 때는 힙의 맨 끝에서 이루어진다. 부모 노드보다 우선순위가 높으면 위치를 바꾸면서 루트노드까지 비교한다.

1. 최대 힙의 맨 끝의 데이터에 30을 가진 노드를 추가한다.
2. 최대 힙이므로 부모 노드의 값이 30보다 작으면 새로 추가한 노드와 위치를 바꿔야 한다. 새로 추가한 노드의 부모 노드 값은 19이므로 새로 추가한 노드의 우선순위가 높다. 따라서 자리를 바꾼다.
3. 데이터 30을 가진 노드와 부모 노드의 값을 비교한다. 부모 노드의 값인 25보다 크므로 자리를 바꾼다.
4. 데이터 30을 가진 노드가 루트 노드가 되어 비교 가능한 노드가 없으므로 연산을 종료한다.

삭제

힙에서 데이터 삭제는 우선순위가 가장 높은 노드를 삭제하는 연산이다.

1. 루트 노드를 삭제한다. 힙의 마지막 노드인 2를 루트노드 자리로 옮긴다.
2. 새로운 루트 노드와 자식 노드 2개(10, 19) 중에서 우선순위가 높은 자식 노드의 값을 비교한다.
3. 바뀐 위치에서 자식 노드와 값을 비교한다. 17보다 우선 순위가 낮으므로 위치를 바꾼다.
4. 비교할 수 있는 자식 노드가 없으므로 연산을 종료한다.

 

정리

우선순위 큐란?

우선순위 큐란 우선순위가 높은 데이터부터 꺼내는 자료 구조로, 각 요소가 우선 순위를 가진다. 우선순위 큐를 이용해 정렬하거나 다익스트라 알고리즘을 구현할 때 사용한다. 우선순위 큐는 주로 힙을 이용해 구현한다.

힙이란?

힙은 완전 이진 트리의 한 종류로, 최대 힙과 최소 힙이 있다. 최대 힙은 부모 노드가 자식 노드의 값보다 크다는 조건을 갖는다. 최소 힙은 부모 노드가 자식 노드의 값보다 작다. 최대 힙과 최소 힙을 이용해 각각 최댓값과 최솟값울 빠르게 찾을 수 있어서 우선순위 큐나 힙 정렬을 하는 데 주로 사용한다.

 

기술 면접 대비 CS 전공 핵심요약집 | 이수진 - 교보문고 (kyobobook.co.kr)