+) [JAVA] 힙정렬 알고리즘 정리 - heap sort

힙정렬

힙정렬을 알아보기 전에 완전이진트리에 대해 알아보자.

우선, 이진트리란, 부모노드로부터 가지가 최대 두개 뻗어나오는, 즉, 자식이 최대 둘인 트리를 일컫는다.

완전이진트리는 다음과 같다.

 

힙이란, 

완전 이진트리 기반의 트리형 자료구조로써 최댓값이나 최솟값을 쉽게 찾아내기 위해 사용된다.

힙에는 최대힙과 최소힙이 있는데,

최대 힙은 부모 노드의 키가 자식 노드의 키보다 같거나 큰 완전 이진 트리이며,

최소 힙은 자식 노드의 키가 부모 노드의 키보다 같거나 큰 완전 이진 트리이다.

 

힙정렬( Heap Sort )이란,

최대힙 트리나 최소힙 트리를 구성해 정렬을 하는 방법이다. 

내림차순 정렬을 하기 위해서는 최대힙을, 오름차순 정렬을 하기 위해서는 최소힙을 구현해야 한다.

 

삽입과 삭제

n개의 정렬해야 할 요소들을 1차원 배열에 기억시킨 후, 힙을 통해 차례대로 삽입한다.

최대힙에서 삭제는, 최댓값부터 삭제한다.