[ch 09-2] 힙의 구현과 우선순위 큐의 완성_1(추가과정, 삭제과정 개념)

[힙의 데이터 저장과정]

- '최소 힙'을 기준으로 설명

  ※ 데이터의 저장 값이 낮은 것이 우선순위가 높음

- 자식 노드 데이터의 우선순위 ≤ 부모 노드 데이터의 우선순위

- 새로운 데이터는 우선순위가 제일 낮다는 가정하에 '마지막 위치'에 저장

  ※ 마지막 위치: 트리의 마지막 레벨의 가장 오른쪽

- 그리고 부모 노드와 우선순위를 비교해가면서, 해당 우선순위 위치를 찾을 때까지 거슬러 올라가면서 교환을 반복

■ 그림(추가과정)

- 완전 이진 트리 예시

- 새로운 노드가 마지막 위치에 생성됨

- 부모 노드와 우선순위 비교

- '2 > 10' 우선순위가 더 높으므로 위치 교환

- 다시 부모 노드와 우선순위 비교

- '2 > 3' 우선순위가 더 높으므로 위치 교환

- 다시 부모 노드와 우선순위 비교

- '2 < 1' 우선순위가 낮으므로 더 이상 비교를 진행하지 않고 종료

■ 그림(삭제과정)

- 추가과정에서 우선순위 변동이 끝난 상태를 기준

- 루트 노드(1)를 삭제

- 마지막 위치에 있던 노드(10)를 루트 노드의 위치로 이동

- 자식 노드간의 우선순위 비교

- '2 > 5' 왼쪽이 더 높으므로 왼쪽 자식 노드와 우선순위 비교

- '2 > 10' 왼쪽 자식 노드의 우선순위가 더 높으므로 위치 교환

- 다시 자식 노드간의 우선순위 비교

- '3 > 18' 왼쪽이 더 높으므로 왼쪽 자식 노드와 우선순위 비교

- '3 > 10' 왼쪽 자식 노드의 우선순위가 더 높으므로 위치 교환

- 자식 노드가 왼쪽만 있으므로 왼쪽 자식 노드와 우선순위 비교

- '30 < 10' 자식 노드보다 우선순위가 높으므로 더 이상 비교를 진행하지 않고 종료

[힙의 데이터 삭제과정]

- 마지막 위치의 노드를 삭제된 루트 노드의 위치로 옮김

  ※ 우선순위 큐는 우선순위가 높은 것을 처리하기 때문에 여기선 루트 노드가 삭제 대상이 됨

- 자식 노드와 우선순위 비교를 통해 해당 우선순위 위치를 찾을 때까지 아래쪽으로 교환을 반복

- 비교를 할 때는 자식 노드 중(왼쪽과 오른쪽) 우선순위가 '높은' 자식 노드와 비교

[삽입과 삭제의 과정에서 보인 성능의 평가]

■ 배열 기반의 데이터 처리 시간 복잡도

1. 저장의 시간 복잡도: O(n)

2. 삭제의 시간 복잡도: O(1)

- 우선순위가 낮은 데이터를 배열에 저장하는 경우, 모든 데이터와 우선순위 비교과정을 거쳐야 하기 때문에 데이터 개수와 동일

- 삭제는 맨 앞에 저장된 데이터를 삭제하면 되기 때문 1회

  ※ 루트 노드 삭제

■ 연결 리스트 기반의 데이터 처리 시간 복잡도

1. 저장의 시간 복잡도: O(n)

2. 삭제의 시간 복잡도: O(1)

- 배열과 동일

■ 힙 기반의 데이터 처리 시간 복잡도

1. 저장의 시간 복잡도: O(log₂n)

2. 삭제의 시간 복잡도: O(log₂n)

- 힙에 저장할 수 있는 데이터의 수는 완전 이진 트리의 높이가 하나 증가할 때마다 2배씩 증가

  ※ 레벨 0-노드 1개(루트 노드) → 레벨 1-노드 2개 → 레벨 2-노드 4개 → ...

- 따라서, 데이터의 수가 2배씩 늘 때마다 비교연산의 횟수는 1회만 증가

  ※ log₂n = '2의 x승(비교연산 횟수) = n개(데이터 개수)