기술 면접 대비 CS 핵심 요약 - 우선순위 큐, 힙

 

 

우선순위 큐(priority Queue)

• 우선순위가 높은 데이터가 먼저 나오는 자료구조
• 큐와 동일하게 삽입, 삭제 연산을 지원한다
• 데이터 삭제 연산을 수행하면 우선순위가 가장 높은 데이터를 얻을 수 있다.
• 구현 방법 : 배열, 연결 리스트, 완전 이진 트리 

 

우선순위 큐의 구현 방식에 따른 시간 복잡도(n: 노드 수)

구현 방법	삽입	삭제
배열(unsorted array)	O(1)	O(n)
연결 리스트 (unsorted linked list)	O(1)	O(n)
배열(sorted array)	O(n)	O(1)
연결 리스트 (sorted linked list)	O(n)	O(1)
힙(heap)	O(log n)	O(log n)

 

 

힙(Heap)

• 완전 이진 트리로, 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조다
• 우선순위 큐를 구현하는데 자주 사용한다
• 최대 힙(max heap) : 부모 노드 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리다
• 최소 힙(max heap) : 부모 노드 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리다

출처 하단 링크

 

1. 삽입 연산

힙에서 데이터를 삽입할 때는 힙의 맨 끝에서 이루어 진다

부모 노드와 우선순위(최댓값 또는 최솟값)를 비교해 부모 노드보다 우선순위가 높으면 위치를 바꾸면서 루트 노드까지 비교한다.

 

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

 

2. 삭제 연산

 

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

삭제한 후에는 루트 노드 자리에 힙의 마지막 노드(마지막 레벨의 가장 오른쪽 노드)를 옮긴 후 힙을 재정렬한다.

 

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

 

참고 링크 :

 

최소 힙 / 최대 힙