Priority Queue   우선순위 큐

(2022-10-20)

1. 우선순위  (Priority Queue)

  ㅇ 임의 순서로 삽입되나 (입력/추가), 일정 순서로 삭제됨 (출력/제거)
      - 입력은, 임의 순서이나, 
      - 출력은, 반드시 일정/정해준 순서를 갖음


2. 우선순위 의 기준

  ㅇ 내림차순 우선순위  (Descending Priority Queue)
     - 항상 제일 큰 항목부터 우선 삭제 (키 값이 클수록 높은 우선순위)

  ㅇ 오름차순 우선순위  (Ascending Priority Queue)
     - 항상 제일 작은 항목부터 우선 삭제 (키 값이 작을수록 높은 우선순위)


3. 우선순위 의 구현 방법이진 힙을 이용한 구현
  ㅇ 피보나치 을 이용한 구현
  ㅇ 배열을 이용한 구현


4. 우선순위 연산

  ㅇ create()  :  우선순위  생성
  ㅇ initialize(q)  :  우선순위  q를 초기화
  ㅇ insert(q, a)  :  우선순위  q에 요소 a를 추가
  ㅇ delete(q)  :  우선순위  q 중 가장 우선순위가 높은 요소를 삭제하고, 이 요소를 반환
     - deleteMax(), deleteMin()
  ㅇ find(q), peek(q)  :  우선순위  q 중 우선순위가 가장 높은 요소를 찾아 반환


5. 우선순위 의 용도

  ※ (주로, 여러 항목 중 최소값/최대값을 찾아야 하는 경우)
  ㅇ 최단 경로 알고리즘 (다익스트라 알고리즘)
  ㅇ 최소 신장 트리 알고리즘 (프림 알고리즘)
  ㅇ 데이터 압축 (허프만 코딩)
  ㅇ 정렬 알고리즘

   1.   2. 우선순위 큐  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"