제자리 힙 정렬

제자리 힙 정렬

728x90

반응형

#define _CRT_SECURE_NO_WARNINGS

#include

int H[100];

int n = 0;

int size = 0;

void printArray()

{

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

{

printf(" %d", H[i]);

}

printf("

");

}

void upHeap(int i)

{

if (i == 1)

return;

if (H[i] <= H[i / 2])

return;

int tmp = H[i];

H[i] = H[i / 2];

H[i / 2] = tmp;

upHeap(i / 2);

}

void downHeap(int i)

{

int larger, tmp;

if ((n < (i * 2)) && (n < (i * 2 + 1))) { // 자식이 없으면 리턴

return;

}

larger = i * 2; //자식이 있으면 왼쪽이 더 크다고 가정

if (n >= i * 2 + 1) { // 오른쪽 자식까지 있으면?

if (H[i * 2 + 1] > H[larger]) {

larger = i * 2 + 1; //비교한 후 더 큰놈 저장

}

}

if (H[i] >= H[larger]) { //부모노드가 더 크면 리턴

return;

}

tmp = H[i]; //부모노드가 더 작으면 스왑

H[i] = H[larger];

H[larger] = tmp;

downHeap(larger);

}

void insertItem(int key)

{

n++;

H[n] = key;

upHeap(n);

}

void rBuildHeap(int i)

{

if (i > n)

return;

rBuildHeap(2 * i);

rBuildHeap(2 * i + 1);

downHeap(i);

return;

}

void inPlaceHeapSort()

{

rBuildHeap(1);

for (int i = n; i >= 2;i--)

{

int tmp;

tmp = H[1];

H[1] = H[i];

H[i] = tmp;

n--;

downHeap(1);

}

}

int main()

{

int tmp;

scanf("%d", &tmp;);

size = tmp;

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

{

scanf("%d", &H;[i]);

insertItem(H[i]);

}

inPlaceHeapSort();

printArray();

return 0;

}

반응형

from http://plug-in-baby.tistory.com/64 by ccl(A) rewrite - 2021-09-19 22:00:41