Chap 06. 우선순위 큐

배열의 단점
- 데이터를 '삽입' 및 '삭제'하는 과정에서 데이터를 한 칸씩 이동하는 연산이 필요하다.
- '삽입의 위치'를 찾기 위해 모든 데이터와 비교하여야한다. 

연결리스트의 단점
 - '삽입의 위치'를 찾기 위해 모든 데이터와 비교하여야한다.

---

위의 단점들을 보완하기 위해 우리는 '완전 이진 트리'인 힙을 사용하여야한다.

< 힙 >
● 배열과 연결리스트의 단점이 '힙'에는 존재하지 않는다.
● 완전 이진 트리 (차곡 차곡 데이터를 쌓는 트리)
● 모든 노드에 저장된 값의 우선 순위는 자식 노드에 저장된 값의 우선순위보다 크거나 같아야한다.
          = 루트 노드가 우선순위가 높아야 한다.

힙의 예시

---

배열과 연결리스트에서는 
삽입을 하기 위해서는 삽입하는 데이터와 저장되어있는 데이터와 모두 비교를 해야한다.
하지만 <힙>은

1. 마지막 인덱스에 새로운 데이터를 저장한다.
2. 부모 노드와 비교한다.
3. 자리를 찾을 때 까지 2번 방법을 반복한다.

그렇다면 데이터 삭제 과정은?

배열은 0번인덱스(우선순위가 가장 높음) 데이터를 삭제하고 모두 한칸씩 당겨줘야한다.
연결리스트에서는 head->next(우선순위가 가장 높은) 데이터를 삭제하고 head->next를 다음 노드를 가리킨다.

힙은 루트 노드(우선순위가 가장 높음)를 제거 한 후,
1. 마지막 노드를 루트 노드로 이동한다.
2. 자식 노드와 비교한다.
3. 자리를 찾을 때  까지 2번 방법을 반복한다.

---

∙ 배열 기반 데이터 삽입의 시간 복잡도 O(n)
∙ 배열 기반 데이터 삭제의 시간 복잡도 O(1)

∙ 연결 리스트 기반 데이터 삽입의 시간 복잡도 O(n)
∙ 연결 리스트 기반 데이터 삭제의 시간 복잡도 O(1)

∙ 힙 기반 데이터 삽입의 시간 복잡도 O(log2 n)
∙ 힙 기반 데이터 삭제의 시간 복잡도 O(log2 n)

---

 

∙ 왼쪽 자식 노드의 인덱스 값  = 부모 노드의 인덱스 값 × 2
∙ 오른쪽 자식 노드의 인덱스 값 = 부모 노드의 인덱스 값 × 2 + 1
∙ 부모 노드의 인덱스 값 = 자식 노드의 인덱스 값 / 2

 

---

∙ 힙은 완전 이진 트리이다.
∙ 힙의 구현은 배열을 기반으로 하며 인덱스가 0인 요소는 비워둔다.
∙ 따라서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다.
∙ 노드의 고유번호가 노드가 저장되는 배열의 인덱스 값이 된다.

---

우선순위 함수

PriorityComp(d1,d2) < 0  => d2가 우선이다.

(1) "내림차순"에서는 값이 작을 수록 우선이다.
==> return d2 - d1;

(2) "오름차순"에서는 값이 클수록 우선이다.
==> return d1 - d2;

---

우선순위 큐는 '힙'이 아니다.
우선순위 큐는 '힙'을 이용한 것이다.
'힙'은 '완전 이진 트리'이다.

우선 순위 큐는 '완전 이진 트리'를 이용한 것이다.