본문 바로가기

자료구조

힙(Heap)정렬 구현

Heap 정렬 구현은 쉽다.

 

kjt9109.tistory.com/entry/%ED%9E%99%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-%EA%B5%AC%ED%98%84-1

 

힙(우선순위 큐) 구현 #1

힙 구현은 곧 우선순위 큐의 완성으로 이어진다. 일반적으로 큐는 FIFO 이다. 하지만 우선순위 큐의 OUT은 들어간 순서 상관 없이 우선순위에 따라 나온다. 힙(Heap)이란? 1. 힙은 '이진트리' 이되 '완

kjt9109.tistory.com

이전에 공부했던 힙을 살펴보면 힙에 데이터를 추가하여 완성 하였을 때

 

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