|힢정렬 개념 | 힢정렬 알고리즘| 힢정렬 분석 |

힢 정렬 알고리즘

  
■ 힢 정렬의 방법                                               이진 트리를 힢 구조로 변경하기 위한 수행과정

▷ 힢을 생성

- 힢의 크기를 배열의 크기로 하고 BuildHeap을 통해 힢조건에 맞게 수정하는 방식

- 배열에 저장은 초기 자료의 순서대로 힢이라 가정하고 트리로 구성함

― 부모 노드는 항상 두 자식 보다 큰 값을 가짐

- BuildHeap을 통해 하나씩 제자리를 찾아 내려보냄

 

 ▷ 제거 동작을 반복 수행

― 가장 큰 값을 갖는 루트에서 제거 동작을 수행하고

― 루트가 없는 힢에서는 최단말 노드가 임시로 루트가 되며 제자리를 찾아 내려가게 됨

― 루트에서 뽑아낸 자료는 임의 배열에 끝에서부터 차례로 저장함