[DataStructure] 우선순위 큐(Priority Queue)와 힙(Heap)의 차이

Queue

• Java의 Queue 인터페이스는 FIFO(First In First Out) 방식의 순차적 자료 구조를 구현
• 즉, 먼저 추가된 요소가 먼저 제거됨.
• Queue 인터페이스는 LinkedList, PriorityQueue, ArrayBlockingQueue 등 다양한 클래스에서 구현

Queue 인터페이스는 큐에 요소를 추가, 제거, 검사하는 여러 메서드를 제공하며, 다음은 가장 일반적으로 사용되는 메서드들이다.

• add(element): 요소를 큐의 맨 뒤에 추가, 큐가 가득 차 있으면 예외를 발생
• offer(element): 요소를 큐의 맨 뒤에 추가, 큐가 가득 차 있으면 false를 반환
• remove(): 큐의 앞에서 요소를 제거하고 반환, 큐가 비어 있으면 예외를 발생
• poll(): 큐의 앞에서 요소를 제거하고 반환합니다, 큐가 비어 있으면 null을 반환
• element(): 큐의 앞에 있는 요소를 제거하지 않고 반환, 큐가 비어 있으면 예외를 발생
• peek(): 큐의 앞에 있는 요소를 제거하지 않고 반환, 큐가 비어 있으면 null을 반환

우선순위 큐(Priority Queue)

• 우선순위 큐는 우선순위에 따라 아이템을 처리 하는 Queue 자료구조로, 주요 동작은 insert, delete, peek이 있다.
• 우선순위 큐는 트리 구조 기반의 이진 트리로 구현된다.
• 이진 트리(Binary tree)는 부모 노드가 최대 2개의 자녀 노드를 가지는 트리를 의미한다.
• 트리 구조는 부모-자녀 계층 구조를 가진다.

힙(Heap)

이미지 출처: https://prepbytes-misc-images.s3.ap-south-1.amazonaws.com/assets/1674109793492-Difference%20Between%20Max%20Heap%20and%20Min%20Heap2.png

• 힙(Heap)은 데이터 구조이며 우선순위 큐의 구현체다.
• Max Heap은 부모 노드의 키 값이 자식 노드들의 키 값보다 크거나 같은 트리를 나타내고, Min Heap은 반대를 의미한다.
• 따라서 힙은 데이터 구조이고, 우선순위 큐는 ADT(Abstract Data Type)으로 추상 데이터 유형이며, 이 둘은 다른 개념이다.

우선순위 큐와 힙의 사용 사례

프로세서 스케줄링

• 운영체제에서 멀티태스킹을 통해 여러 프로세스가 CPU를 번갈아가며 실행한다.
• 프로세스들은 Ready Queue에서 기다리며 이때 각 프로세스의 우선순위가 결정된다.
• 프로세스가 CPU에서 실행되는 조건은 해당 프로세스의 작업이 끝날 때나 타임 슬라이스로 인해 우선순위가 높은 다음 프로세스가 실행될 때이다.

heap sort

• 정렬을 할때도 사용할 수 있다.
• 시간 복잡도는 Best-case & Average-case: O(n log n), Worst-case: O(n log n)이다.
• 공간 복잡도는 O(1)이다. (in-place sorting, modifies the original array)

힙 메모리와 데이터 구조의 힙은 다르다.

• 힙 메모리는 동적으로 할당된 객체들을 저장하는 RAM 메모리 영역을 의미한다.

참고

• https://youtu.be/P-FTb1faxlo?si=gsMYK4x_Is6-wTr7