(오름차순 기준)

힙에서 가장 큰 값인 루트를 꺼내고 남은 요소에서 다시 가장 큰 값을 구하는 것을 반복
선택 정렬을 응용한 알고리즘
루트를 없앤 다음 다시 힙을 만들기 위해 요소를 알맞은 위치로 보내는 순서
루트를 꺼냄
마지막 요소를 루트로 이동
자기보다 큰 값을 가지는 자식 요소와 자리를 바꾸며 아래쪽으로 내려가는 작업을 반복
자식의 값이 더 작거나 잎에 다다르면 작업 종료
힙 정렬 알고리즘
/* 오름차순 힙 정렬 프로그램 */
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
/*--- a[left] ~ a[right]를 힙으로 만드는 함수 ---*/
static void downheap(int a[], int left, int right)
{
int temp = a[left]; /* 뿌리 */
int child;
int parent;
for (parent = left; parent < (right + 1) / 2; parent = child) {
int cl = parent * 2 + 1; /* 왼쪽 자식 */
int cr = cl + 1; /* 오른쪽 자식 */
child = (cr <= right && a[cr] > a[cl]) ? cr : cl; /* 큰 값 선택 */
if (temp >= a[child])
break;
a[parent] = a[child];
}
a[parent] = temp;
}
/*--- 힙 정렬 함수 ---*/
void heapsort(int a[], int n)
{
int i;
for (i = (n - 1) / 2; i >= 0; i--)
downheap(a, i, n - 1);
for (i = n - 1; i > 0; i--) {
swap(int, a[0], a[i]);
downheap(a, 0, i - 1);
}
}
첫 요소(가장 큰 값)를 꺼내는 작업 : O(1)
나머지 요소들을 다시 힙으로 만드는 작업 : O(log n)