자료구조 알고리즘 힙정렬(Heap Sort, 힙정렬) 정리

안녕하세요, 츄르 사려고 코딩하는 집사 코집사입니다.

자료구조 고급 알고리즘인 Merge Sort, Quick Sort에 이어 Heap Sort 입니다.

Heap Sort란??

힙정렬은 힙이라는 특수한 자료구조를 사용하는 정렬 알고리즘

힙은 최소힙과 최대힙이 있는데 값이 저장되는 방향만 반대일 뿐 성질은 똑같습니다.

힙(Heap)??

힙(Heap)은 이진트리로서 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 꽉 채워져 있습니다.

힙(Heap)의 모든 노드는 하나씩의 값을 갖고 있는데 아래의 힙성질을 만족합니다.

1) 각 노드의 값은 자신의 자식의 값보다 작다

   (힙에 값이 같은 원소가 두 개 이상 있는 경우에는 "작다" 대신 "작거나 같다")

리프 노드는 자식이 없으므로 위 성질은 논리적으로 자동 만족이 되고, 모든 노드가 위의 성질을 만족하면, 이진트리의 루트 노드에는 최소값이 자리하게 된다. <- 이것이 최소힙입니다.

최대힙은 루트 노드에는 최대값이 자리하게 되는 것을 말합니다.

힙정렬(Heap Sort)의 순서

1) 먼저 주어진 배열을 Heap으로 만든다.

2) Heap에서 가장 작은 값을 차례로 하나씩 제거하면서 Heap의 크기를 줄여나간다.

3) 나중에 힙에 아무 원소도 남지 않으면 Heap Sort가 끝난다.

<소스 코드>