Heap Sort(힙 정렬) 구현

Heap(힙) 이라는 자료구조를 이용해 정렬을 하는 알고리즘입니다.

일반적으로 버블정렬, 삽입정렬, 선택정렬은 O(n^2)의 시간복잡도 이지만

힙정렬은 힙의 구조상 시간복잡도가 O(nlogn)으로 상대적으로 효율적인 알고리즘입니다. 

n^2 시간복잡도의 sort 알고리즘에 비해서 좀 구현이 까다로울 수 있지만 그래도 힙의 구조를 이해하면 쉽게 구현하실 수 있을꺼같아요.

아 그리고.... 힙소트는 힙이라는 자료구조를 만들어둔 상태에서 소트를 하는 알고리즘이기 때문에

입력을 받을때부터 Insert함수에서 힙으로 만들어줍니다.

이 밑에 있는 요상한 것이 바로 힙(Heap)이라는 건데요.

구조적으로 바이너리 트리를 만족하고,

현재 노드v의 원소의 value는 노드v의 left, right(즉 자식이겠죠.)의 원소보다 value값이 작은 조건을 만족하는 형태를 가집니다.

그리고 이걸 배열로 구현하게 된다면

현재 자기자신의 노드의 index를 i라 하면, 왼쪽 노드의 인덱스는 index*2, 오른쪽 노드는 index*2+1가 됨을 알수있죠. 밑에 그림에서 보면 last node의 index를 가리켜야 한다고 하는데요. 이 index는 바로 heap의 size와 같다는걸 알 수 있죠. (자세한 Heap Data Structure 설명은 다음에 포스팅 하도록 하겠습니다.)

/*

Heap_Sort

Made by Hahahia

*/

#include <iostream>

using namespace std;

 

int heap[1000000],heapSize; // heap DataStructure, heapsize

 

void Insert(int element) // heap에 원소를 삽입하는 함수

{

        heapSize++;

        heap[heapSize] = element;

        int now = heapSize; // heapSize = index

        while(heap[now/2] > element) // 부모의 원소가 자식의 원소보다 큰 경우

        {

               heap[now] = heap[now/2]; // 자리를 바꿔요

               now /= 2;

        }

        heap[now] = element; // 최종적으로 힙에 들어갈 자리를 잡아요.

}

int main()

{

        int n;

        int size;

        int temp;

        int index;

        heapSize = 0;

        cout << "input n : " ;

        cin >> n;

        int element;

        for(int i=1; i<=n; i++)

        {

               cout << "input " << i << " : ";

               cin >> element;

               Insert(element); // 힙정렬의 특징으로 힙 구조를 만들어둬야 합니다.

        }

        cout << "Heap Sort \nresult : ";

        size = n;

        for(int i=1; i<=n-2; i++){

               temp = heap[1];

               heap[1] = heap[size];

               heap[size] = temp; // heap size 감소

               size--;

               index = 1;

               while(1) // heap 으로 재정렬을 합니다.

               {

                       if(size==2)

                       {

                              if(heap[index] <= heap[index+1])

                              {

                                      temp = heap[index];

                                      heap[index] = heap[index+1];

                                      heap[index+1] = temp;

                                      break;

                              }

                       }

                       if(heap[index] >= heap[index*2] && (heap[index*2] <= heap[index*2+1]))

                       {

                              temp = heap[index];

                              heap[index] = heap[index*2];

                              heap[index*2] = temp;

                              index = (index*2);

                       }

                       else if(heap[index] >= heap[index*2 + 1] && (heap[index*2] >= heap[index*2+1]))

                       {

                              temp = heap[index];

                              heap[index] = heap[index*2+1];

                              heap[index*2+1] = temp;

                              index = (index*2 + 1);

                       }

 

                       if(((index*2) >= size) || ((heap[index] <= heap[index*2] && heap[index] <= heap[index*2+1])))

                               break;

               }

        }

        for(int i=n; i>=1; i--){

               cout << heap[i] << " ";

        }

        cout << endl;

        return 0;

}

 

실행결과