힙 정렬(Heap Sort)
힙 정렬은 힙을 이용하여 정렬을 합니다.
루트 노드에 있는 값이 정렬 순서상 가장 앞서는 원리를 이용합니다.
그러기 위해선 힙을 이용해야겠죠.
힙은 간단히 얘기하자면 트리중에 하나인데 완전 이진 트리입니다.
즉 모든 노드 저장된 값들이 자식 노드 보다 크거나 같아야합니다. 루트노드가 가장 큰것이죠.
값은 우선순위가 될 수도 있고 그 자체 Value(값)일 수도 있습니다.
최대 힙과 최소 힙이 있습니다.
최대 힙은 루트노드로 갈 수록 값이 커지는 트리이고
최소 힙은 루트노드로 갈 수록 값이 작아지는 트리입니다.
즉 힙을 이용해서 정렬 대상을 힙에 삽입을 하고 차례대로 삭제하여 꺼내면 정렬 완료입니다. (우선순위 큐)
힙 정렬 함수
우선 정렬 대상을 인자로 전달합니다. arr[]배열이 되겠죠.
Heap을 heap변수로 선언합니다.
해당 힙을 초기화를 진행합니다.
진행 후 for문을 통해 정렬할 데이터 개수만큼 돌려서
힙에 집어넣습니다.
집어 넣은 것을 차례대로 빼면 정렬 완료이기 때문에
HDelete함수를 이용해서 하나씩 빼서 데이터들을 배열에 넣습니다(반환)
힙에 대한 소스 코드입니다.
#include "UsefulHeap.h"
void HeapInit(Heap * ph, PriorityComp pc) //힙초기화
{
ph->numOfData = 0; //개수 0
ph->comp = pc; //비교함수 넣기
}
int HIsEmpty(Heap * ph) //비었는지 확인
{
if(ph->numOfData == 0) //개수가 0이면 True
return TRUE;
else
return FALSE;
}
int GetParentIDX(int idx) //부모 인덱스 반환 ( 인덱스의 나누기 2)
{
return idx/2;
}
int GetLChildIDX(int idx) //왼쪽 자식 노드 인덱스 반환(곱하기 2)
{
return idx*2;
}
int GetRChildIDX(int idx) //오른쪽 자식 노드 인덱스 반환(곱하기2+1)
{
return GetLChildIDX(idx)+1;
}
int GetHiPriChildIDX(Heap * ph, int idx) //높은 우선순위의 자식 인덱스값 반환
{
if(GetLChildIDX(idx) > ph->numOfData) // 자식 노드가 없다면(단말노드(자식 노드 없음)의 왼쪽 노드의 인덱스는 개수보다 크다)
return 0;
else if(GetLChildIDX(idx) == ph->numOfData) // 왼쪽 자식 노드가 마지막 노드라면
return GetLChildIDX(idx);
else // 왼쪽 자식 노드와 오른쪽 자식 노드의 우선순위를 비교
{
// if(ph->heapArr[GetLChildIDX(idx)].pr
// > ph->heapArr[GetRChildIDX(idx)].pr)
/// 왼쪽 자식노드 인덱스 해당하는 값의 우선순위(pr)이 만약에 오른쪽 자식 우선순위보다 크다면
if(ph->comp(ph->heapArr[GetLChildIDX(idx)],
ph->heapArr[GetRChildIDX(idx)]) < 0)
return GetRChildIDX(idx); // 우선순위 숫자 pr이 작을수록 우선순위가 큰 것이므로 오른쪽 자식 노드
else
return GetLChildIDX(idx);
}
}
void HInsert(Heap * ph, HData data)
{
int idx = ph->numOfData+1; //삽입할 인덱스는 총 개수 +1
while(idx != 1)//인덱스가 1이 아니면 (최상위 노드가 아니라면) 삽입할 위치를 찾음 부모노드 대소 비교 위로올라가면서 인덱스 1을 만날 때 까지
{
// if(pr < (ph->heapArr[GetParentIDX(idx)].pr))//새로운 노드의 우선순위가 부모노드의 우선순위보다 높다면 교체
if(ph->comp(data, ph->heapArr[GetParentIDX(idx)]) > 0)
{
ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];//부모노드를 한 레벨 내림
idx = GetParentIDX(idx);//새 노드의 위치를 저장
}
else
{
break;
}
}
ph->heapArr[idx] = data;//최종 새 노드의 데이터를 idx 에 저장
ph->numOfData += 1;//증가
}
HData HDelete(Heap * ph)
{
HData retData = ph->heapArr[1]; // 삭제할 데이터 임시 저장
HData lastElem = ph->heapArr[ph->numOfData]; //힙의 마지막 노드 저장
int parentIdx = 1;//parentIdx에 마지막 노드가 저장될 위치정보가 담김
int childIdx;
//루트 노드의 우선순위가 높은 자식 노드를 기반으로 시작 반복문 while(childIdx = GetHiPriChildIDX(ph, parentIdx))
{
// if(lastElem.pr <= ph->heapArr[childIdx].pr)
//마지막 노드의 우선순위가 우선순위 높은 자식노드의 우선순위 숫자보다 작다면 즉 우선순위가 크다면
if(ph->comp(lastElem, ph->heapArr[childIdx]) >= 0)
break;
ph->heapArr[parentIdx] = ph->heapArr[childIdx];//마지막 노드보다 우선순위가 높으니까 자식 노드를 한단계 위로 올림
parentIdx = childIdx;//마지막 노드를 한단계 내림
}
ph->heapArr[parentIdx] = lastElem;
ph->numOfData -= 1;
return retData;
}
#ifndef __USEFUL_HEAP_H__
#define __USEFUL_HEAP_H__
#define TRUE 1
#define FALSE 0
/*** Heap의 정의 ****/
#define HEAP_LEN 100
typedef char HData;
// d1의 우선순위가 높다면 0보다 큰 값
// d2의 우선순위가 높다면 0보다 작은 값
// d1과 d2의 우선순위가 같다면 0을 반환
typedef int PriorityComp(HData d1, HData d2);
typedef struct _heap
{
PriorityComp * comp;
int numOfData;
HData heapArr[HEAP_LEN];
} Heap;
/*** Heap 관련 연산들 ****/
void HeapInit(Heap * ph, PriorityComp pc);
int HIsEmpty(Heap * ph);
void HInsert(Heap * ph, HData data);
HData HDelete(Heap * ph);
#endif
