힙 정렬 (Heap Tree Sort)

힙 정렬 (Heap Tree Sort)

HEAP TREE란? (HEAP SORT)

• 최소값 또는 최대값을 빠른 시간 안에 접근할 수 있도록 만들어진 자료구조.
• 트리의 최상위 노드는 항상 최소값 또는 최대값을 저장하고 있음.
• PUSH 프로세스 이후에 POP 으로 정보를 빼오면 SORTING된 상태로 저장됨. (가장 최소값 또는 최대값을 콜해옴과 동시에 트리의 최상위 노드를 그 다음 최소값 또는 최대값으로 업데이트하기 때문)

• 따라서, 부모 노드의 우선순위가 자식 노드의 우선순위보다 항상 높다!

PUSH 함수

• 데이터의 추가.
• 새로 추가된 노드는 PARENT NODE 와 경쟁함.
• 만약 노드가 PARENT NODE 보다 우선하면 SWAP.
• RECURSIVE until PARENT > 0

POP 함수

• 데이터 꺼내오기.
• 최대값 또는 최소값의 위치는 항상 최상위 노드.
• 비어진 최상위 노드의 자리에 LAST NODE를 먼저 넣어놓고, 그 LAST NODE의 우선 순위를 자식 노드들과 경쟁 비교해서 SWAP.

Sample Code 

//HEAP TREE
int Heap_Push_Minheap(int *heap, int size, int *lastnode, int d)
{
    int node, parent, tmp;
 
    if (*lastnode == size) return 0;
 
    heap[++(*lastnode)] = d;
    node = *lastnode;
    parent = node / 2;
 
    while (parent > 0)
    {
        if (heap[node] < heap[parent])
        {
            tmp = heap[node];
            heap[node] = heap[parent];
            heap[parent] = tmp;
 
            node = parent;
            parent = node / 2;
        }
        else break;
    }
    return 1;
}
 
int Heap_Pop_Minheap(int *heap, int *lastnode, int*d)
{
    int node, child, lchild, rchild;
 
    *d = heap[1];
    heap[1] = heap[(*lastnode)--];
 
    node = 1;
    lchild = 2;
    rchild = 3;
 
    while (lchild <= *lastnode)
    {
        if (*lastnode == lchild) child = lchild;
        else child = ((heap[lchild]) < (heap[rchild]) ? lchild : rchild);
 
        if (heap[child] < heap[node])
        {
            tmp = heap[child];
            heap[child] = heap[node];
            heap[node] = tmp;
 
            node = child;
            lchild = node * 2;
            rchild = node * 2 + 1;
        }
        else break;
    }
    return 1;
}
 
 
int Heap_Push_Maxheap(int *heap, int size, int *lastnode, int d)
{
    int node, parent, tmp;
 
    if (*lastnode == size) return -1;
 
    heap[++(*lastnode)] = d;
    node = *lastnode;
    parent = node / 2;
 
    while (parent > 0)
    {
        if (heap[node] > heap[parent])
        {
            tmp = heap[node];
            heap[node] = heap[parent];
            heap[parent] = tmp;
 
            node = parent;
            parent = node / 2;
        }
        else break;
 
    }
    return 1;
 
}
int Heap_Pop_Maxheap(int *heap, int *lastnode, int*d)
{
    int node, child, lchild, rchild, tmp;
 
    *d = heap[1];
    heap[1] = heap[(*lastnode)--];
 
    node = 1;
    lchild = 2;
    rchild = 3;
 
    while (lchild <= *lastnode)
    {
        if (lchild == *lastnode) child = lchild;
        else child = ((heap[lchild]) > (heap[rchild]) ? (lchild) : (rchild));
 
        if (heap[node] < heap[child])
        {
            tmp = heap[node];
            heap[node] = heap[child];
            heap[child] = tmp;
 
            node = child;
            lchild = node * 2;
            rchild = node * 2 + 1;
        }
        else break;
 
    }
    return 1;
 
}
 
void Heap_Sort(int *data, int cnt, int order)
{
    int i, ret, lastnode = 0;
 
    HEAP_PUSH Heap_Push[2] = { Heap_Push_Maxheap, Heap_Push_Minheap };
    HEAP_POP Heap_Pop[2] = { Heap_Pop_Maxheap, Heap_Pop_Minheap };
 
    for (i = 0; i < cnt; i++)
    {
        Heap_Push[order](data - 1, MAX_DATA, &lastnode, data[i]);
    }
 
    for (i = cnt - 1; i >= 0; i--)
    {
        Heap_Pop[order](data - 1, &lastnode, &ret);
        data[i] = ret;
    }
}