Heap Sort
- 힙이란 우선순위큐를 표현한 완전이진트리의 배열식 표현을 의미한다.
* 기본적으로 힙의 i번 요소의 자식은 (2*i)번과 (2*i +1)번이다.
- 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법
* 최대힙 : 부모노드가 항상 자식노드보다 크며 완전이진트리에 가까운 이진트리를 말함
* 최소힙 : 최대힙과 반대. 부모노드가 자식노드보다 항상 작은 경우
- 힙이 수행할 수 있는 조작
삽입
[insert : 트리의 끝부분에 값을 삽입하는 함수]
[upHeap : 삽입된 값의 위치를 찾아주는 함수]
삭제
[deletMax : 트리의 뿌리 부분에 존재하는 최대값을 제거하는 함수]
[downHeap : 대소관계에 의해 트리를 재구성하는 함수]
- 내림차순 정렬을 위해선 최대힙을 오름차순 정렬을 위해선 최소힙을 구성하면 됨
* 최대 힙 정렬 예
1. n개의 노드에 대한 완전이진트리를 구성한다
2. 최대힙을 구성한다 (최대힙 : 부노드가 자노드보다 큰 트리)
3. 배열 마지막값과 배열 첫번째 값을 교환한다
4. 배열의 길이를 1 줄인 후 2,3을 반복한다
-> 2번을 수행하게되면 배열의 첫번째 값에 가장 큰 값이 오게 되며 3번을 통해 큰값을 맨 뒤로 보낸 후 맨 뒷값을 제외하고 2,3번을 다시 반복하는 것이다.
복잡도 -
평균, 최선, 최악의 경우 전부 :
구현 -
결과 -
반응형