우선순위 Queue vs Heap

Y39·2023년 4월 1일
0

toBeProgrammer

목록 보기
75/88

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 메모리는 아니다!!
profile
System.out.print("Bold")

0개의 댓글