개념
- 힙 트리의 특징을 이용하여 정렬
(힙 트리에 원소들을 전부 삽입 후 힙의 루트에 있는 값을 이용하여 정렬)
- 힙 트리는 완전이진트리구조를 가진 자료구조
- 추가적인 메모리를 전혀 필요로 하지 않음
- 항상 O(nLogn)정렬의 성능
- 선택정렬과 비슷
(매번 원소를 순환하면서 정렬하느냐 아니냐의 차이)
* 힙트리는 첫번째 출처, 힙정렬은 두번째 출처에 알기쉽게 설명되어 있다.
원소 (16,14,10,8,7,9,3,2,4,1)를 정렬할 경우 (최대힙 기준)
힙트리에 삽입
1. 최상위 루트인 16을 추출
2. 추출되어 비어진 최상위 루트에 마지막 노드 1로 채움
3. 최대힙 특성에 맞춰 힙 트리를 재정렬
4. 재정렬 후 최상위 루트가 된 14를 추출
더이상 트리에 값이 남아있지 않을때까지 위 과정을 반복하면 완료
트리 참고
힙 트리 - 나무위키
최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다. 루트 노드를 제거한다.루트 자리에 가장 마지막 노드를 삽입한다.[3]올라간 노드와 그의 자식 노드(들)와 비교한다.조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다. 최대 힙부모보다 더 큰 자식이 없으면 교환하지 않고 끝낸다.부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환하면 된다.부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환한다. 최소 힙부모보다 더 작은 자식이 없
namu.wiki
정렬 알고리즘 - 힙 정렬
힙 정렬힙(heap)힙 정렬을 하기 전에 우선 힙에 대해 알아보자.힙은 현재 개발된 가장 작은 자료구조들 중 ...
blog.naver.com
Tree (트리)
그래프의 일종. 데이터 항목의 한 묶음을 세그먼트라고 하는데, 이 세그먼트 사이의 연결을 나뭇가지처럼 표현한 것이 트리 구조다. 1. 트리 종류 a. 이진 트리 (binary tree) - 자식노드가 최대 2개면 이진 트..
chipmunk-plump-plump.tistory.com
RememberCook 9월 28일 정식 출시!
두번째 게임인 RememberCook이 출시되었습니다. 귀여운 캐릭터들이 나오는 간단한 게임이며 플레이어의 공간인지능력을 테스트하는 게임입니다. 아래 링크를 통해 다운 받으실 수 있으니 많은 관��
chipmunk-plump-plump.tistory.com
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| Optimal BST (최적 이진 탐색 트리) (9) | 2020.05.12 |
|---|---|
| binary search tree (이진 탐색 트리) (9) | 2020.05.11 |
| Merge Sort (병합정렬) (0) | 2020.04.20 |
| Quick Sort (퀵 정렬) (5) | 2020.04.20 |
| Insertion Sort (삽입정렬) (1) | 2020.04.19 |
