[알고리즘] 힙 정렬(Heap Sort)이란?

먼저 힙 정렬에 대해 다루기 전에 "힙"에 대한 이해가 필요합니다. 힙에 대해 알고 싶다면 아래 링크를 참고하시면 도움됩니다.

힙(Heap) 자료구조 힙(Heap)이란 ? 완전 이진 트리의 일종으로, 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 만들어진 자료구조입니다.

힙을 사용하는 이유는 최댓값과 최솟값을 찾기 위해 배열을 사용하는 경 hstory0208.tistory.com 힙 정렬(Heap Sort) 힙 정렬 알고리즘은 삽입과정 없이 삭제과정만이 이뤄집니다. 최대힙(max heap)을 구현한뒤, 루트 노드를 삭제하여 마지막 노드가 루트 노드가 되어 최대힙의 규칙에 맞게 재구조화 되며 정렬합니다.

힙 정렬 알고리즘은 주로 다음과 같은 경우에 유용하게 사용됩니다. 최댓값과 최솟값을 구할 때 최대 k만.....