heap sort
- 힙 정렬이란?
- build 시간복잡도
- example
들어가기 전
전과 면접 때 힙정렬을 엉망으로 설명했던 기억이 나서 다시 한 번 복습할 겸 블로그를 작성해보려고 한다.
자료구조 'heap'이란
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
- 최댓값 또는 최솟값을 쉽게 추출할 수 있는 자료구조
그렇다면 완전 이진 트리는 무엇일까?
- 각 노드가 최대 2개의 자식 노드를 갖는 트리
children of A[k] is "A[2k+1] and A[2k+2]"
- 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다.
- 최하단 레벨의 노드는 좌측 노드부터 차례대로 삽입되어 있어야 한다.
heap sort - build
면접 때 힙 정렬 build의 시간복잡도를 θ(NlogN)이라고 당당하게 말했던 것이 부끄러워서 다시 한 번 정리해보려고 한다.
우선, 면접 때 말한 방식대로 n개를 insert 하는 방식으로 heap을 구현하면 nlogn의 시간복잡도를 갖는 것이 맞다. 하지만 정렬하지 않고 우선 완전이진트리를 만들어놓고 level이 큰 노드부터 차례대로 percolate down 방식을 사용하면 시간복잡도를 θ(n)으로 만들 수 있다.
사실 면접 때 정렬에 있어서 θ(nlogn)보다 절대 빠를 수 없다고 확신했었다. 모든 요소를 읽는 데에만 n번의 연산이 필요한데 이를 θ(n)으로 정렬까지 할 수 있을 것이라고는 생각지도 못했다. 그래서 이 부분을 복습하면서 더 재미있었던 것 같다.
- 정렬 전에 그냥 배열에 넣는다.
- leaf node의 부모 노드부터 시작한다.
- 해당 노드를 자식 노드와 비교해가며 자리를 바꿔나간다. (percolate down)
example
A = [4, 1, 8, 7, 3, 3', 5, 2, 9] 를 heap sort 하는 과정을 살펴보자.
가장 깊이가 낮은 노드의 부모 노드들부터 차례대로 자식들과 비교해가며 자리를 찾아가면 된다.
이때 level이 i인 노드는 최대 개가 존재하며, d-1번의 연산으로 제 자리를 찾아갈 수 있다.
증명)
시간복잡도 정리
- search : O(n)
- insert : O(log n)
- DeleteMax : O(log n)
- Build : θ(n)
깔끔하게 heap sort를 복습할 수 있어서 좋네요! 관련 문제도 풀어봐야겠어요!!~~