Heap 정렬 구현은 쉽다.
이전에 공부했던 힙을 살펴보면 힙에 데이터를 추가하여 완성 하였을 때
Root노드에는 우선순위가 가장 큰 데이터가 오게된다.
따라서 힙 구조에 Root 노드 데이터만 빼서 뺀 순서대로 정렬하면 데이터를 자연스럽게 정렬 된다.
Root 노드 데이터만 빼는 TakeOut 함수를 구현한다.
HeapTakeOut()
1
2
3
4
5
6
7
8
9
10
11
12
|
HData HeapTakeOut(HeapStruct *useHstr)
{
HData retData;
retData = useHstr->heapData[1];
if (HeapDelete(useHstr, retData) != -1)
{
return retData;
}
return -1;
}
|
cs |
Arg로 가져온 힙 구조체에 1번 데이터를 삭제시킨후 Return시킨다.
(1번 데이터는 Root 노드)
데이터 TakeOut이 구현되었으므로 힙 정렬을 구현해보자
HeapSort()
1
2
3
4
5
6
7
8
9
10
11
12
|
void HeapSort(HeapStruct *useHstr, HData *contArr)
{
int idx = useHstr->heapNode;
if (useHstr->heapNode > 0)
{
for (int i = 0; i < idx; i++)
{
contArr[i] = HeapTakeOut(useHstr);
}
}
}
|
cs |
데이터가 없을때 까지 TakeOut 하여 배열에 저장하면 된다.
HeapStructure에 데이터를 저장 후 정렬 할때 HeapSortArray에 우선순위 맞게 정렬한다.
실행 화면
'자료구조' 카테고리의 다른 글
병합 정렬 구현 (병합) #2 (0) | 2021.11.14 |
---|---|
병합 정렬 구현 (분열) #1 (0) | 2021.11.14 |
힙(우선순위 큐) 구현 #2 (0) | 2021.01.08 |
힙(우선순위 큐) 구현 #1 (0) | 2021.01.08 |
수식트리의 구현 #2 (0) | 2020.12.30 |