Heap과 Heapsort
- 최악의 경우 시간복잡도 O(nlog2n)
- Sorts in place - 추가 배열 불필요 (mergesort와 다르다!)
- 이진 힙(binary heap) 자료구조를 사용
Heap은
1) complete binary tree
2) heap property 를 만족
max heap property : 부모는 자식보다 크거나 같다 = 위에 노드의 값이 더 커야 한다.
min heap property : 부모는 자식보다 작거나 같다
트리는 계층적 관계를 표기하기 위해서 사용
이진트리는 한 부모가 두개의 자식을 가지고 있는 것
full binary tree : 모든 레벨에 노드들이 꽉 차 있어야 함
(단일 노드만 있어도 풀 바이너리 트리이다!)
complete binary tree : 마지막 레벨을 제외하면 완전히 차 있고, 마지막 레벨에는 가장 오른쪽부터 연속된 몇 개 노드가 비어있을 수 있음.
(이거는 왼쪽은 거진 메꿔져 있어야 정상.)
동일한 데이터를 가지더라도 서로 다른 모양의 힙일 수 있다.
(힙 조건만 만족하면 데이터 위치는 중요하지 않음)
힙은 일차원 배열로 표현가능하다. A[1...n]
루트 노드 A[1].
A[i]의 부모 = A[i/2]
A[i]의 왼쪽 자식 = A[2i]
A[i]의 오른쪽 자식 = A[2i + 1]
1의 왼쪽 자식은 2
1의 오른쪽 자식은 3
2의 부모는 1
3의 부모는 1
이런 식으로 계산 가능하다.
Heap을 이용해서 정렬을 하기 위한 기본 연산 : Max Heapify
: 전체를 힙으로 만들어라.
- 트리의 전체 모양이 complete binary tree여야 한다.
유일하게 루트만이 heap property를 만족하지 않음. (부모가 없으니까)
- 왼쪽 subtree는 그 자체로 heap이고,
- 오른쪽 subtree도 그 자체로 heap일 때!!
만약에 루트만 힙 조건을 만족하지 않을 경우,
조건을 만족시키기 위해 자식들 중 더 큰 쪽이 루트보다 크면 교환한다.
그런 식으로 밑까지 내려 보냄.
요렇게 heap 조건을 만족시키는 이진 트리로 만듬.
교수님 따르릉 하고 끝남 -.-)...
댓글
댓글 쓰기