이번에 공부 할 내용은 힙 정렬이다.

Heap Sort 란?

간단하다 Heap 을 이용하여 정렬하는 방식을 이야기한다.

그럼 Heap 이란 무엇인가?

The Heap Data Structure

완벽하게 정리 된 위 포스트를 읽어보면 좀 더 정확하고 확실하게 이해할 수 있겠지만

간단하게 되짚어 보고 가자

힙(Heap)은 최솟값 또는 최댓값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로한 자료구조이다.

일단 힙은 두가지 종류가 있다.

1. 높은 값을 우선순위로 가지는 최대 힙 (부모 노드가 항상 자식노드 보다 커야 함)
2. 낮은 값을 우선순위로 가지는 최소 힙 (부모 노드가 항상 자식노드 보다 작아야 함)

또, Heap 은 두가지 조건이 필요한데

1. 구조 조건 - 완전 이진 트리를 만족해야 한다.
2. 순서 조건 - Partial Order를 만족해야 한다.