Heapsort

Heap

0. concepts

• 완전 이진트리의 일종 ( 완전 이진 트리란 마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있으며 마지막 레벨의 node들은 가능한 한 왼쪽부터 채워져 있는 구조를 말한다. )
• 반 정렬 상태(느슨한 정렬 상태) 를 유지함. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도! 걍 부모가 더 크다
  
  
• 종류 2개 ; max-heaps(부모가 자식보다 같거나 큰 것. root가 젤 큰애^^) , min-heaps(수업에서 x)

 ->array 저장 가능

• array에 저장될 수 있다 레벨 순서대로 저장~
• root = A[1]
• i 노드의 parent 인덱스 = i/2의 정수 (언더) (3/2 = 1)
• i 노드의 left 인덱스 = 2i
• i 노드의 right 인덱스 = 2i+1

• height of a node : 해당 노드서부터 리프까지 노드개수 (걍 아래에잇는 노드 개수) 위 그림에서 14의 height=2
• height of a heap : 루트노드의 height. Θ(lgn)이다 (n=element 개수. 힙은 complete binary라서 Θ(lgn)이 보장됨)

1. algorithm

a. max-heapify

- 계속 힙 성질 유지하도록 한다 (부모가 큰거)

• float down - 해당 노드가 자식보다 작으면, 자식중에서 더 큰 애랑 자리를 바꾼다 ~.~ 그렇게 계속 내려간다 ^^

- running time ?

T(n) ( n=서브트리 노드의 개수 )

- 값 교환하는데에는 Θ(1)

- 최대 h번 함 (lgn)

-> O(lgn)

 

 

b. building a heap (걍 a를 모든 힙 구성요소에 적용되도록 하는 것)

- 슈도코드

- 러닝타임

1. upper bound

: O(lgn)*n/2(의 다운바운드) = O(nlgn)

2. tight bound

: 한 노드에서 실행되는 max-heapify연산 횟수는 모두 다르다 ! (height의 차이도 중요!! height작은애들이 훨씬 많으니까 일괄적으로 해버리면 부정확)

각 층에서의 노드 개수는

나머지 구하는 과정은 복잡

답만적으면 tight bound는 O(n)

 

c. extract-max

: 젤 큰 친구를 뺍니다

- 빼는 연산 연산: O(1). 걍 부모 빼면 됨

- 맨 마지막(인덱스. 걍 리프중 가장 오른쪽) 애를 부모에 넣음

- 복구하기 : O(lgn) (부모에서 max-heapify연산함)

-> O(lgn)

 

d. heapsort

: 힙으로 정렬해서 최댓값 차례로 빼내서 배열을 정렬하는 것

1.  A[1...n]에 대해 max-heap을 만든다 => O(n)

2. extract-max를 n번 한다 => O(nlgn)

- 수도코드

 

2. priority queues

* 큐 = first in first out. (high priority 가진애(=먼저 들어간 애)가 먼저 나온다)

(우선순위가 높다=더앞에 있다. 더 먼저나온다)

우선순위 큐 = 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것 , 먼저 처리 되는 것. 힙으로 구현가능! heap-based

(여기선 우선순위가 크다 = 숫자가 더 크다!)

 

-> 우선순위 큐 연산들

1. INSERT(S,key) : set S에 key를 넣는다

-사이즈를 하나 늘리고, 맨 마지막요소에 -무한대를 둔다 (그럼 젤 작은값이 되겟지요)

그리고 해당 값을 key로 증가시켜준다!(바꿔준다) = INCREASE-KEY(S,x,key)를 한다

-> O(lg n )

(수도코드)

2. MAXIMUM(S) : largest key를 가진 element 리턴한다 (걍젤큰거리턴. =우선순위가젤큰거 리턴)

- 걍 맨뒤꺼 읽으면 되서 O(1)

3. EXTRACT-MAX(S) : 가장 큰친구를 삭제하고 리턴한다 (=deque)

-맨위꺼 삭제하고 max-heapify를 한다 (그리고 머 마지막꺼 지워주겟지, 그리고 삭ㅈㅔ햇던 젤큰거 리턴하겟지 모)

-> O(lg n) (=max-heapify)

4. INCREASE-KEY(S,x,k) : S에서 x의 키를 k로 증가시킨다 (x=인덱스. x의 키를 k로 바꿔줌)

- 걍 해당 엘리먼트값을 k로 바꿔준담에 max-heapify

-> O(lg n)