[자료구조] 2. 우선순위 큐(Priority Queue)

2021. 12. 6. 17:14

우선순위 큐(Priority Queue)


일반적인 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 이런 큐의 특성과 달리 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고 우선순위가 가장 높은 데이터가 가장 먼저 나오게 된다. heap으로 구현되어 있다.

  • 우선순위 큐의 이용 사례
    • 시뮬레이션 시스템
    • 네트워크 트래픽 제어
    • 운영 체제에서의 작업 스케쥴링
    • 수치 해석적인 계산
  • 우선순위를 구현할 수 있는 방법 : Array, LinkedList, heap

  • heap으로 구현된 이유 : 힙의 경우 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 계속 이루어진다. 이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 갯수는 2배 증가하며, 비교 연산 횟수는 1회 증가한다. 즉 삭제나 삽입 모두 최악의 경우에는 O(log2n) 의 시간 복잡도를 가집니다.

 


Heap구조

  • 배열로 구현되어 있다.
  • 완전 이진 트리
    1. 마지막 레벨을 제외한 모든 노드가 채워져있어야함
    2. 모든 노드들은 왼쪽부터 채워져있어야함
  • 최대 값 혹은 최솟 값을 빠르게 찾는다.
  • 부모 노드가 자식 노드보다 우선순위가 높다
  • 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 → 모든 숫자가 정렬되어 있으면 삽입 삭제 시 정렬을 완전히 맞춰야돼서 시간이 오래걸림

max-heap

  • 최대 힙은 부모 노드가 자식 노드보다 크다(루트노드로 올라갈 수록 값이 크다)

min-hip

  • 최소 힙은 부모 노드가 자식 노드보다 작다(루트노드로 올라갈 수록 값이 작다)

 


Heap의 데이터 삽입

  1. 우선순위가 낮다고 생각하고 맨 끝 노드에 삽입한다.
  2. 우선순위가 맞지 않으면 부모와 계속 비교하면서 위치를 바꿔준다.

Heap의 데이터 삭제

  1. 루트 노드를 삭제한다.(우선순위 큐의 삭제 의미는 최상단 노드를 삭제)
  2. 마지막 노드를 루트 노드로 옮긴다.
  3. 루트 노드의 자식 노드 중 우선순위가 높은 쪽과 비교하며 진행한다.

Heap 배열로 구현

 

  • 힙을 저장하는 표준적인 자료구조는 배열 이다.
  • 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
  • 힙에서의 부모 노드와 자식 노드의 관계
    • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
    • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
    • 부모의 인덱스 = (자식의 인덱스) / 2

 

참고

https://st-lab.tistory.com/205#size

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

'CS > Data Structure' 카테고리의 다른 글

[자료구조] 3. Hash Table  (0) 2021.12.07
[자료구조] 1. Stack & Queue  (0) 2021.11.16

BELATED ARTICLES

more