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

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

※ 힙(Heaps)

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

1. 루트 노드의 제거

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

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

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

※ 응용

1. 우선 순위 큐 (priority queue)

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

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

2. 힙 정렬 (heap sort)

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

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

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

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

728x90

from http://prerain.tistory.com/42 by ccl(S) rewrite - 2021-10-18 12:27:13