힙(heap) 정렬 알고리즘

1. 힙 자료구조

 최솟값 혹은 최댓값을 빠른 시간에 접근하도록 만들어진 자료구조

2. 자료구조의 특징

1) 각 노드의 값이 자식노드의 값들보다 크거나 작다

2) 완전 이진 트리(complete binary tree)이다

3) 트리의 마지막 층에 있는 이파리 노드들은 왼쪽부터 꽉 차 있는 형태를 가진다

4) 순서는 위->아래, 왼쪽->오른쪽

5) 왼쪽 노드와 오른쪽 노드의 순서는 상관 없다

3. 노드

k는 높이, i는 정수이고 i번째 노드라고 할때,

힙 크기 : 2^k -1

부모 노드 : i/2

왼쪽 자식 노드 : 2i

오른쪽 자식 노드 : 2i+1

4. 알고리즘 구현

 힙 자료구조의 특징(완전 이진트리)을 이용한 알고리즘으로, 데이터를 모두 힙에 넣었다가 다시 꺼내서 정렬하는 것이다. 

1) DownHeap 함수의 내용

bigger : 큰 값을 가진 인덱스를 저장

DownHeap(arr, i), arr는 힙 내용을 저장한 배열, i는 입력하고자 하는 노드의 인덱스

① 입력받은 노드와 그 왼쪽 자식 노드를 비교, 

왼쪽 자식노드가 더 크면 bigger 변수에 자식노드의 값을 저장

② 입력받은 노드와 그 오른쪽 자식 노드를 비교, 

오른쪽 자식노드가 더 크면 bigger 변수에 자식노드의 값을 저장

③ 입력받은 노드가 자식노드들보다 크면 입력노드의 값을 bigger 변수에 저장하고,

위의 두 과정 중 하나에 해당하면 입력받은 노드의 값과 자식노드의 값을 서로 바꾼 다음

DownHeap(arr, bigger)를 다시 호출한다

2) 알고리즘 구현

#include <iostream>

using namespace std;

const int intmax = 1024;

void swap(int &arr1, int &arr2)

{

int temp = arr1;

arr1 = arr2;

arr2 = temp;

}

void DownHeap(int * arr, int node_index, int whole_node_num)

{

int bigger;

int leftchild = 2 * node_index + 1;

int rightchild = 2 * node_index + 2;

if (leftchild < whole_node_num + 1 && arr[leftchild] > arr[node_index])

bigger = leftchild;

else

bigger = node_index;

if (rightchild < whole_node_num + 1 && arr[rightchild] > arr[bigger])

bigger = rightchild;

if (bigger != node_index)

{

swap(arr[node_index], arr[bigger]);

DownHeap(arr, bigger, whole_node_num);

}

}

void HeapSort(int * arr, int whole_node_num)

{

whole_node_num = whole_node_num - 1;

for (int i = whole_node_num / 2 - 1; i >= 0; i--)

DownHeap(arr, i, whole_node_num);

}

int main()

{

int arr[intmax];

int whole_node_num;

cout << "전체 노드 개수 : ";

cin >> whole_node_num;

if (!whole_node_num) return 0;

for (int i = 0; i < whole_node_num; i++)

cin >> arr[i];

HeapSort(arr, whole_node_num);

for (int i = 0; i < whole_node_num; i++)

cout << arr[i];

return 0;

}