Data Structure - Priority Queue & Heap

1.. Priority Queue(우선순위 큐) 란?

• 데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나감
  

• 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하며,
  힙(heap)으로 구현하는 것이 가장 효율적이다.
  

• Priority Queue는 ADT(Abstract Data Type)으로, 실제 구현은 없고 개념적인 설명만 있음
• 반면에 HEAP은 구현을 하는 구현체이며 Data Structure이다.

2.. HEAP 이란?

• 완전 이진 트리(Complete Binary Tree)의 일종으로, 우선순위 큐를 위해 만들어진 자료구조
• 여러 개의 값들 중 최대값 혹은 최소값을 빠르게 찾아내도록 만들어진 자료구조
• 힙 트리에서는 중복된 값을 허용(이진 탐색 트리에서는 중복된 값 허용 X)
• 최악의 경우 시간복잡도는 O(nlogn)

3.. HEAP 의 종류

1. Max Heap(최대 힙)
   • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
2. Min Heap(최소 힙)
   - 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
   

4.. HEAP 의 구현

• 힙을 저장하는 표준적인 자료구조는 배열
• 쉬운 구현을 위하여 배열의 첫번째 index는 사용되지 X
• 힙에서 부모노드와 자식 노드의 관계
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2

5.. HEAP 삽입

• 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 이어 삽입
• 새로운 노드를 부모 노드들과 교환하여 힙의 성질을 만족시켜야함

6.. HEAP 삭제

• 최대 힙에서 최대값은 루트 노드이므로, 루트 노드가 삭제됨
• 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
• 힙을 재구성한다.