알고리즘10. Heapsort

4. Sorting

4-4. Heapsort 

 

Heap and Heapsort

Heap: 우선순위 큐 구현 방법

 

max-heap 기준1. insert()2. findMax()3. deleteMax()3가지 함수를 이용해 정렬

 

Heap data structure는 특수 속성을 가진 binary tree이다.

• Heap Structure →구조
• Partial order tree property(부분 정렬 트리 속성) →순서

 

Heap Structure

binary tree T는 다음 조건을 만족하는 경우에만 heap structure (h = 트리의 height)

1. T is complete at least through depth h-1 →depth h-1까지 트리가 꽉 차 있다

2. All leaves are at depth h or h –1 →모든 leaf의 깊이는 h 또는 h-1이다.

3. All paths to a leaf of depth h are to the left of all paths to a leaf of depth h-1 →삽입 시 왼쪽부터 채워지고, 삭제 시 오른쪽부터 삭제

☞ 이러한 트리를 left-complete binary tree라고도 부른다.(=일반적인 complete binary tree)

 

Partial order tree property

• parent(v).key ≥ v.key
• 임의 노드의 키 값이 자식 노드의 키 값보다 크거나 같다.

 

Example: Heaps (or not)

구조조건 만족X→ 힙 아님

구조조건 만족, 순서 조건이 나타나 있지 않음→ 힙 아님

left-complete binary tree구조, 순서 조건 나타나 있음(Maxheap조건 만족)→ 힙

 

 

Heapsort Strategy

정렬할 elements가 heap에 배열된 경우,

• 반복적으로 root의 element를 제거함으로써 역순으로 정렬된 시퀀스를 만들 수 있다.
• 나머지 요소를 재배열하여 partial order tree 속성을 재설정하는 등의 작업을 수행한다.

 

How?

Maxheap기준으로 하기 때문에 delete = deleteMax()