반응형
※ 참고자료
- 유튜브(동빈나)
https://www.youtube.com/watch?v=iyl9bfp_8ag&t=331s
힙 정렬이란?
- 완전 이진트리의 일종이다.
- 현재 완전히 정렬된 상태가 아니며, 중복 값을 허용한다.
- 병합 정렬과 퀵 정렬만큼 빠른 속도를 가지고 있다.
- 힙의 정의를 알아야 한다.
힙이란?
힙을 알기 위해선 이진트리를 먼저 알아야 한다.
이진트리 : 모든 노드의 자식 노드가 2개 이하인 트리
완전 이진트리 : 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리. 즉, 이진트리의 노드가 중간이 비지 않고 빽빽이 가득 찬 구조
힙 : 최솟값이나 최댓값을 빠르게 찾아내는 이진트리를 기반한 트리
최대 힙 : 부모 노드가 자식 노드보다 큰 힙
최소 힙 : 부모 노드가 자식 노드보다 작은 힙
문제에서 만약 입력이 크기 n인 배열로 주어진다면
-> 크기가 n인 완전 이진트리를 하나 준다.
-> 힙의 구조 조건을 만족한다.
이런 문제의 경우 힙의 구조 조건을 따로 만족해줄 필요 없이 순서 조건만 만족시켜주면 된다.
최대 힙으로 만들기
- n개의 노드에 대한 완전 이진트리를 구성한다. 이때 루트 노드부터 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 구성한다.
- 최대 힙을 구성한다. 최대 힙이란 부모 노드가 자식 노드보다 큰 트리를 말하는데, 단말 노드를 자식 노드로 가진 부모 노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
- 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
- 2와 3을 반복한다.
출처: https://zeddios.tistory.com/56 [ZeddiOS]
출처 : https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC
힙 정렬의 시간복잡도 : O(n*longn)
힙 정렬 장점
병합정렬과 다르게 추가적인 배열이 필요하지 않아 메모리가 효율적이다.
항상 시간복잡도가 (n*longn)으로 보장된다.
반응형