[Data Structure & Alogrithm] Priority Queue & Heap
📝 Priority Queue (우선순위 큐)
📌 핵심 요약
"데이터가 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조"
📌 설명
-
우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조다.
-
우선순위 큐는 배열, 연결리스트, 힙을 이용하여 구현할 수 있다.
-
배열기반으로 우선순위 큐를 구현하면, 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시키면 된다.
-
하지만 삽입&삭제 연산에서의 shift 연산 오버헤드가 발생한다. 또한 적절한 삽입 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위 비교를 진행해야할 수도 있다.
-
연결리스트 기반으로 우선순위 큐를 구현하면, 배열과 같이 shift 오버헤드는 발생하지 않지만 우선순위에 따른 적절한 삽입 위치를 찾아야하는 단점은 똑같다.
-
배열과 연결리스트 기반 우선순위큐의 단점으로 인해 우선순위 큐는 힙이라는 자료구조를 이용해서 구현하는 것이 일반적이다.
📝 Heap
📌 핵심 요약
"힙은 우선순위 큐 구현에 어울리는 자료구조이다. 힙은 완전 이진트리 형태이며 모든 노드는 자식 노드보다 우선 순위가 높다는 특징을 갖는다. 값이 클수록 우선순위가 높은 힙을 Max 힙, 값이 작을수록 우선순위가 높은 힙을 min 힙이라고 한다."
📌 설명
-
Heap은 완전 이진 트리 자료구조이다. 우선순위 큐 구현에 딱 어울린다.
-
Heap의 모든 노드는 자식 노드보다 우선순위가 높다.
-
Min Heap : 루트 노드로 올라갈수록 저장된 값이 작아지는 Heap
-
Max Heap : 루트 노드로 올라갈수록 저장된 값이 커지는 Heap
📌 시간복잡도
- 탐색
O(1): 루트 노드를 얻으면 된다. - 삽입
O(logN): 원소를 힙의 “마지막 위치”에 삽입하고, 힙 구조를 유지하는데 걸리는 시간 - 삭제
O(logN): 루트 노드를 제거하고, 힙의 “마지막 위치에 있는 노드”를 루트 노드 자리에 삽입하고, 힙 구조를 유지하는데 걸리는 시간- 힙의 “마지막 위치” : 완전 이진 트리 구조인 힙에서 마지막 레벨의 가장 오른쪽 위치다.