(오름차순 기준)

힙

KakaoTalk_20210912_152223056.jpg

힙 정렬

/* 오름차순 힙 정렬 프로그램 */
#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(n log n)