[WEEK03] 힙 / 우선순위 큐

1. 힙이란?

특징

- 힙은 일종의 반정렬 상태 (느슨한 정렬상태)를 유지함

- 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 정도 (혹은 반대)

- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진트리

 

장점

- 시간복잡도가 좋은편

- 힙 정렬이 가장 유용한 경우는 전체를 정렬하기보다 가장 큰 값 몇개만 필요할 때임

 

시간복잡도

- 힙 트리의 전체 높이 = log(n) / 하나의 요소 개수가 N개

- 따라서 T(n) = O(nlogn)

 

2. 우선순위 큐?

특징

- 우선순위의 개념을 큐에 도입한 자료구조

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

- 우선순위 큐는 배열, 연결리스트, 힙으로 모두 가능하나 힙으로 구현하는 것이 가장 효율적임

- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

 

3. 힙의 종류

최대 힙 (max heap)

최소 힙 (min heap)



 

 

3. 힙의 구현

특징

- 힙을 저장하는 표준적인 자료구조는 배열

- 힙에서 특정위치에 새로운 노드가 추가되어도 노드 번호는 변화하지 않음

 

관계

- 부모 인덱스 = x

- 왼쪽 자식 인덱스 = x * 2 / 오른쪽 자식 인덱스 = x * 2 + 1

 

 

3. 힙의 추가와 삭제

추가

1. 힙에 새로운 요소가 들어오면 새로운 노드를 힙의 마지막 노드에 이어서 삽입

2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킴

힙의 추가

 

삭제

1. 최대 힙에서 최댓값은 루트노드이므로 루트 노드 삭제

2. 삭제된 루트 노드에는 힙의 마지막 노드 가져옴

3. 힙을 재구성

힙의 삭제

 

 

[출처]

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html