백준(baekjoon)(BaekJoon)코딩 2751번:힙 정렬(Heap Sort) 답

//배열의 개수를 2등분 한다. 한쪽은 배열 개수가 전체에서 2로 나눈 수, 다른 한 쪽은 전체에서 그 수를 뺀 수.

// 각각의 첫번째를 포인터로 지정한다.

// 각 []    [] 배열 끼리 최소 값을 찾는다.

// 최소값을 찾은 것 서로 비교

#include <stdio.h>
#include <iostream>
using namespace std;
 
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
 
void maxHeapify(int array[], int size, int index)
{
int largest = index;    // Initialize the largest as root
int left = (index << 1) + 1;   // left = 2*index + 1
int right = (index + 1) << 1;    // right = 2*index + 2
 
// See if left child of root exists and is greater than root
if (left < size && array[left] > array[largest])
largest = left;
 
// See if right child of root exists and is greater than the largest so far
if (right < size && array[right] > array[largest])
largest = right;
 
// Change root, if needed
if (largest != index)
{
swap(&array[largest], &array[index]);
maxHeapify(array, size, largest);
}
}
 
void heapSort(int array[], int size)
{
int i;
// Create an initial max heap.
// Start from bottommost and rightmost internal mode and
// heapify all internal modes in bottom up way
for (i = (size - 2) / 2; i >= 0; i--)
maxHeapify(array, size, i);
 
// Repeat reduce and heapify steps while heap size is greater than 1.
while (size > 1)
{
// The largest item in Heap is stored at the end.
swap(&array[0], &array[size - 1]);
// Reduce heap size
size--;
// Heapify the root of tree
maxHeapify(array, size, 0);
}
}
 
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
 
int main(int argc, char** argv)
{
int num;
cin >> num;
int *data = new int[num];
for (int i = 0; i < num; i++)
{
cin >> data[i];
}
 
heapSort(data, num);
printArray(data, num);
 
delete[] data;
return 0;
}