[자료구조&알고리즘] 힙(Heaps(2))

※ 힙(Heaps)

- 최대 힙에서 원소를 삭제하는 순서

1. 루트 노드의 제거

2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치

3. 자식 노드들과의 값 비교, 아래로 이동

 - 자식이 두개가 있을 경우는 더 큰 값을 기준으로 이동

 

※ 응용

1. 우선 순위 큐 (priority queue)

 - Enqueue 할 때 '느슨한 정렬'을 이루고 있도록 함: O(logn)

 - Dequeue 할 때 최댓값을 순서대로 추출: O(logn)

2. 힙 정렬 (heap sort)

 - 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입: O(logn)

 - 삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제: O(logn)

 - 원소들이 삭제된 순서가 원소들의 정렬 순서임

 - 정렬 알고리즘의 복잡도: O(nlogn)