[Heap Sort] 힙 정렬

※ 참고자료

- 유튜브(동빈나)

https://www.youtube.com/watch?v=iyl9bfp_8ag&t=331s

 

 

힙 정렬이란?

1. 완전 이진트리의 일종이다.
2. 현재 완전히 정렬된 상태가 아니며, 중복 값을 허용한다.
3. 병합 정렬과 퀵 정렬만큼 빠른 속도를 가지고 있다. 
4. 힙의 정의를 알아야 한다.

 

힙이란?

힙을 알기 위해선 이진트리를 먼저 알아야 한다.

이진트리 : 모든 노드의 자식 노드가 2개 이하인 트리

 

완전 이진트리 : 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리. 즉, 이진트리의 노드가 중간이 비지 않고 빽빽이 가득 찬 구조

 

힙 : 최솟값이나 최댓값을 빠르게 찾아내는 이진트리를 기반한 트리

최대 힙 : 부모 노드가 자식 노드보다 큰 힙

최소 힙 : 부모 노드가 자식 노드보다 작은 힙

 

문제에서 만약 입력이 크기 n인 배열로 주어진다면

-> 크기가 n인 완전 이진트리를 하나 준다.

-> 힙의 구조 조건을 만족한다.

 

이런 문제의 경우 힙의 구조 조건을 따로 만족해줄 필요 없이 순서 조건만 만족시켜주면 된다.

 

최대 힙으로 만들기

1. n개의 노드에 대한 완전 이진트리를 구성한다. 이때 루트 노드부터 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 구성한다.
2. 최대 힙을 구성한다. 최대 힙이란 부모 노드가 자식 노드보다 큰 트리를 말하는데, 단말 노드를 자식 노드로 가진 부모 노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
4. 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)으로 보장된다.