힙 정렬 (Heap Sort)

Heap Sort는 Heap 이라는 자료구조를 이용해 정렬을 하는 알고리즘이다.

 

• Heap 이란 완전 이진 트리 형태로 Paren Node 는 Child Node 보다 반드시 큰(작은) 값을 가진다.

 

• Heap Sort의 경우 항상 O( N log(N) ) 의 시간복잡도를 가진다.

 

• 우선 모든 원소를 최대(최소) Heap에 삽입한다.( O(logN) )

 

• Heap 트리의 최대(최소) 값을 출력한다.( O(1) )

 

• 최대(최소) 값을 제거하고 Heap을 재배열 한다.( O(logN) )

 

• Heap이 빌때가지 반복한다.( O(N) )

 

• Stable 을 만족하지 않는다.

 

 #include <iostream>
  #include <vector>
  #include <algorithm>

  using namespace std;

  int main() {
   vector<int> v = { 3,1,4,1,5,9 };

   while(!v.empty()){
     //최대힙을 만든다
     make_heap(v.begin(), v.end());					
     //힙의 root를 마지막 원소로 이동시킨다.
     pop_heap(v.begin(), v.end());
     //마지막 원소를 출력하고 제거한다.
     cout << v.back() << ' ';
     v.pop_back();
   }

   return 0;
  }

 

 

실제로 Heap을 구현 할때는 주로 Array을 이용한다. 이때 index를 1부터 시작했을때,

• Right Child Node의 index 값 : Parent Node의 index 값 * 2
• Left Child Node의 index 값 : Parent Node의 index 값 * 2 + 1
• Parent Node의 index 값 : Child Node의 index 값 / 2