[알고리즘] 3-3. 분할 정복을 이용한 정렬 (2)

힙정렬

1. 최악의 경우 시간복잡도 : O(nlog2n)

2. sorts in place : 추가 배열 불필요 [공간 복잡도 이득]

3. 이진 힙 자료구조 이용

 

힙의 정의

 

힙 : 완전이진트리이면서 힙 속성 만족

[힙은 동일 데이터를 가진 서로 다른 힙이 존재 가능하며, 유일하지 않다]

 

[최대 힙 : 부모는 자식보다 크거나 같다.]

[최소 힙 : 부모는 자식보다 작거나 같다.]

 

전이진 트리   : 모든 레벨에 노드들이 꽉 차있는 형태

완전이진트리 : 마지막 레벨 제외하면 완전히 차있고, 마지막 레벨에 가장 오른쪽부터 연속된 노드가 비어있을수있음

 

 

힙의 표현

1. 일차원 배열로 표현 : A[1...n]

2. 루트 노드 : A[1]

3. A[i]의 부모 : A[i/2]

4. A[i]의 왼쪽 자식 : A[2i]

4. A[i]의 오른쪽 자식 : A[2i+1]

 

 

전체를 힙으로 : MAX-HEAPIFY

-> 트리 전체 모양은 완전 이진 트리

[두 자식들 중 더 큰쪽이 자신보다 크면 교환]

 

루트만 힙 속성 만족안함

-> 왼쪽 부트리와 오른쪽 부트리가 그 자체로 힙인 경우

 

//1. MAX-HEAPIFY - recursive

MAX-HEAPIFY(A, i)
//노드i가 루트 노드인 서브트리를 heapify
//루트 노드에 대한 heapify : MAX-HEAPIFY(1)

{
 if there is no child of A[i]
  return;
 k <- index of the biggest child of i;
 
 if A[i] >= A[k]
  return;
 exchange A[i] and A[k];
 MAX-HEAPIFY (A,k);
};

 

//2. MAX-HEAPIFY - iterative

MAX-HEAPIFY(A, i)
{
 where A[i] has a child do
 k <- index of the biggest child of i;
 if A[i] >= A[k]
  return;
 exchange A[i] and A[k];
 i=k;
 end.
}

---

힙 정렬

1. 주어진 데이터로 힙을 만든다.

2. 힙에서 최대값(루트)를 가장 마지막 값과 바꾼다.

3. 힙의 크기가 1 줄어든 것으로 간주한다. [가장 마지막 값은 힙의 일부가 아닌 것으로 간주]

4. 루트노드에 대해서 HEAPIFY(1)한다.

5. 반복

 

// 힙 정렬 시간 복잡도

HEAPSORT(A)
 BUILD-MAX-HEAP(A) : O(n)
  for i <- heap_size downto 2 do : n-1 times
   exchange A[1] <-> A[i] : n-1 times
   heap_size <- heap_size -1 : O(1)
   MAX-HEAPIFY(A,1) : O(log2n)
   
   -> O(nlog2n)

 

우선순위 큐

1. 최대 우선순위 큐

: INSERT(x) - 새로운 원소 x를 삽입

: EXTRACT_MAX() : 최대값을 삭제하고 반환

 

2. 최소 우선순위 큐

: INSERT(x) - 새로운 원소 x를 삽입

: EXTRACT_MIN : 최소값을 삭제하고 반환

 

MAX-HEAP-INSERT (A, key) {
 heap_size = heap_size+1;
 A[heap_size] = key;
 i = heap_size;
  while (i>1 and A[PARENT(i)] < A[I]) {
   exchange A[i] and A[PARENT(i)];
   i = PARENT(i);
 }
}

 

EXTRACT-MAX(A) {
 if heap-size[A] <1
  then error "healp underflow"
 max <- A[1]
 A[1] <- A[heap-size[A]]
 heap-size[A] <- heap-size[A] -1
 MAX-HEAPIFY (A,1)
 return max;
}