[백엔드 기술면접] 우선순위 큐와 힙(Priority queue and heap)
서론
우선순위 큐와 힙의 개념과 차이, 사용 사례를 설명합니다! 힙이 어떻게 동작하는지 알아봅시다.
본론
Priority queue(우선순위 큐)
큐와 유사하지만 우선순위가 높은 아이템이 먼저 처리됨
우선순위 큐 주요 동작
- insert(아이템을 넣는 것,우선순위 정보도 같이 넣어야함)
- delete(우선순위가 가장 높은 아이템을 뺌)
- peek(우선순위 delete와 비슷하지만 제거는 하지 않음)
우선순위 큐 동작 방식 설명
Heap(힙)
힙은 주로 이진트리(binary tree) 기반으로 구현이됨.
트리(tree): 부모-자녀처럼 계층적인 형태를 가지는 구조
이진트리(binary tree): 자녀가 최대 두 개인 트리
힙은 max heap과 min heap이 있는데 max heap은 부모 노드의 키(key)가 자식 노드(들)의 키(key)보다 크거나 같은 트리이다. 사진에 동그라미를 노드라고 부른다. 숫자는 키라고 생각하면 된다. min heap부모 노드의 키(key)가 자식 노드(들)의 키(key)보다 작거나 같은 트리를 말한다.
max heap
min heap
힙 주요 동작
- insert
- delete
- peek
Pirotriy Queue와 Heap 관계
힙(heap)의 키(key)를 우선순위(priority)로 사용한다면 힙은 우선순위 큐(priority queue)의 구현체가 된다.
Priority queue = ADT(실제 구현이 아닌 개념적인 것을 설명함) Heap = data structure(구현까지 설명함 )
사용사례
process scheduling(프로세스 스케쥴링) heap sort(힙 정렬) heap 메모리의 힙은 다르다. 관련 없음!!!