7강. 힙정렬(Heap Sort)(2)

[ 목차 ]

1. 힙 구조 만들기

2. 힙 구조 만들기의 수행시간

3. 최대값 추출 Extract-Max

4. 힙 소트 Heap Sort의 Pseudo Code

5. 힙 소트의 수행시간

 

1. 힙 구조 만들기

1) Build-Max-Heap(a)

2) MAX-HEAPIFY(A,i)는 자식을 가지는 마지막 노드부터 시작

 

2. 힙 구조 만들기의 수행시간

 

3. 최대값 추출 Extract-Max

1) Heap에서 가장 큰 값을 제거하고 Max-Heap 구조를 복원하는 연산

2) root에 있는 최대값을 추출하고 트리의 가장 마지막에 있는 값을 root로 옮기고 다시 MAX-HEAPIFY

2) 수행시간

 

4. 힙 소트 (Heap Sort)의 Pseudo Code

 

5. 힙 소트의 수행시간