[자료구조] 8일차 우선순위 큐의 방법과 힙

우선순위 큐란?

: 출력 연산 시 가장 우선순위가 높은 원소를 출력한다.

 

📌 단순하게 생각해보기

 

❗ 높은 숫자가 우선순위라고 가정함.

= 출력값의 빈자리는 당겨짐

 

 

📌 우선순위 큐를 단순한 접근 방법으로 구현한 경우

- 입력 : O(1)
- 출력 : O(n)
우선순위가 가장 높은 원소를 찾는 과정과, 원소 제거가 비효율적임.

힙

: 최솟값 또는 최댓값을 빠르게 찾기 위해 고안된 완전 이진 트리

 

최대 힙

: 부모 노드는 항상 자식 노드보다 큰 값을 갖고 있음.

최소 힙

: 부모 노드는 항상 자식 노드보다 작은 값을 갖고 있음.

 

 

  import heapq  

파이썬의 heapq 모듈로 최소 힙 사용

 

📌 최대 값이 필요한 경우

값을 저장할 때 -1을 곱한 값을 저장하면 됨. -1을 곱함으로서 최댓값과 최솝값이 반전된다는 점을 이용 (단, 수(number)일 때만 유효)
ex) 5 > 4 → -5 < -4

 

힙: 자료 입력하기

• 완전 이진 트리의 특성을 유지해야함.
• 입력된 자료는 항상 마지막 레벨의 가장 오른쪽 자리에 채워진다.

예시1)

• 부모노드가 자신보다 더 작은 값이 될 떄까지 계속해서 자리를 변경함.

 

 

예시2)

최악의 경우

: 새로운 최솟값이 입력되는 경우 → 루트 노드까지 거슬러 올라가게 됨.

: 이때 발생하는 연산 횟수는 트리의 높이와 비례하므로 O(logn)의 시간 복잡도를 가진다.

 

 

 

힙 : 자료 출력하기

• 힙에서 출력되는 자료는 무조건 루트 노드

 

 

최악의 경우

: 맨 마지막 원소가 가장 큰 값을 가진 경우

: 자리를 바꾸는 연산의 횟수 = 트리의 높이

: O(logn)의 시간 복잡도를 가짐.

 

 

우선순위 큐의 구현