관리 메뉴

Kim-Baek 개발자 이야기

힙 정렬 (Heap Sort) 본문

컴퓨터 공학/자료구조, 알고리즘

힙 정렬 (Heap Sort)

킴백 개발자 2020. 9. 29. 10:00

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

 

반응형

'컴퓨터 공학 > 자료구조, 알고리즘' 카테고리의 다른 글

tree, heap, binary tree, avl tree, red-black tree  (0) 2020.10.11
리스트, 스택, 큐  (0) 2020.10.10
힙 정렬 (Heap Sort)  (0) 2020.09.29
퀵 정렬 (Quick Sort)  (0) 2020.09.28
병합 정렬 (Merge Sort)  (0) 2020.09.27
삽입 정렬 (Insertion Sort)  (0) 2020.09.26
0 Comments
댓글쓰기 폼