우선순위 Queue vs Heap

Priority quere

: 큐와 유사하지만 우선순위가 높은 것부터 수행

• insert
  : 우선순위도 함께 삽입
• delete
  : 우선 순위가 높은 것부터 삭제
• peek
  : 우선순위가 높은 것부터 가져옴

동작방식

• 우선순위 (5, 20, 10) 삽입
• 삭제시 (20 > 10 > 5) 순서대로 진행

Heap

• 이진트리로 구현됨
• minHeap: root가 가장 작음, maxHeap: root가 가장 큼
• 주요 동작
  • insert
    : key 값에 따라 트리 구조로 삽입됨
  • delete
    : root 부터 삭제
  • peek
    : root 부터 꺼냄

Priority queue와 Heap 관계

• Priority queue = ADT
  • 직접 구현되지 않은 추상적 개념
• Heap = data structure
  => Priority queue는 성능이 가장 좋은 Heap을 통해서 구현됨

사용

• Process scheduling
• heap 정렬
• !! heap 메모리는 아니다!!