[자료구조] 힙정렬(Heap Sort)이란?

힙정렬이란

2022.10.13 - [📚 자료구조 및 알고리즘/힙] - [자료구조] 힙(Heap)이란?

[자료구조] 힙(Heap)이란?

합병 정렬방식은 비록 최악의 경우 연산 시간과 평균 연산 시간 모두 O(nlogn)이지만, 정렬할 레코드 수에 비례하여 저장 공간이 추가로 필요하다. 힙 정렬(heap sort)은 일정한 양의 저장 공간만 추가적으로 필요한 동시에, 최악의 경우 평균 연산 시간이 O(n log n)이다. 하지만, 힙 정렬은 합병 정렬보다 약간 느리다. 힙 정렬의 핵심 알로리즘은 이름처럼 힙를 사용한다. 그중에서도 최대 힙 구조를 이용한다. 따라서, 최대 히프가 되도록 레코드를 재조정 후 루트를 하나씩 빼내면서 정렬을 하는 기법이다.

 

즉, 힙정렬의 알고리즘은

1. 정렬할 n개의 요소를 최대 힙에 삽입
2. 한번에 하나씩 힙에서 삭제하여 저장
3. 힙 크기 감소 및 재조정
4. n-1 반복

• 힙에 삽입하거나 삭제할 때 시간이 O(logN)만큼 소요되고 요소의 개수가 n개이므로 전체적으로 O(NlogN)의 시간이 걸린다.
• 힙정렬이 최대로 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때이다.

---

 

 

Adjust 함수

• 왼쪽 및 오른쪽 서브 트리가 모두 히프인 이진 트리에서 시작해 이진 트리 전체가 최대 히프가 되도록 재조정
• 연산 시간 : O(d) (d는 트리의 깊이)

// 최대 힙(max heap) 삭제 함수
element delete_max_heap(HeapType *h){
  int parent, child;
  element item, temp;

  item = h->heap[1]; // 루트 노드 값을 반환하기 위해 item에 할당
  temp = h->heap[(h->heap_size)--]; // 마지막 노드를 temp에 할당하고 힙 크기를 하나 감소
  parent = 1;
  child = 2;

  while(child <= h->heap_size){
    // 현재 노드의 자식 노드 중 더 큰 자식 노드를 찾는다. (루트 노드의 왼쪽 자식 노드(index: 2)부터 비교 시작)
    if( (child < h->heap_size) && ((h->heap[child].key) < h->heap[child+1].key) ){
      child++;
    }
    // 더 큰 자식 노드보다 마지막 노드가 크면, while문 중지
    if( temp.key >= h->heap[child].key ){
      break;
    }

    // 더 큰 자식 노드보다 마지막 노드가 작으면, 부모 노드와 더 큰 자식 노드를 교환
    h->heap[parent] = h->heap[child];
    // 한 단계 아래로 이동
    parent = child;
    child *= 2;
  }

  // 마지막 노드를 재구성한 위치에 삽입
  h->heap[parent] = temp;
  // 최댓값(루트 노드 값)을 반환
  return item;
}
https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

1. 루트값을 item에 임시 저장
2. temp에는 마지막 노드의 값을 저장하고 size 1감소
3. 현재 루트 노드의 왼쪽 자식 노드부터 비교 시작
4. 만약 왼쪽보다 오른쪽 노드가 더 크다면 child값을 증가시켜서 오른쪽 노드로 변경
5. 2개의 자식보다 루트노드가 크면 while문 탈출
6. 부모노드가 자식노드보다 작으면 그 자식노드와 교환 ( 부모노드에 자식노드값 대입 )
7. 한 단계 아래로 이동해주고 마지막노드를 재구성한 위치에 삽입

---

 

힙정렬 시간복잡도

힙 트리의 전체 높이가 거의 log₂n(완전 이진 트리이므로)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 log₂n만큼 소요된다. 요소의 개수가 n개 이므로 전체적으로 O(nlog₂n)의 시간이 걸린다.
T(n) = O(nlog₂n)