자료구조(heap)

• heap 자료구조는 완전 이진트리구조이다.
• heap 자료구조는 우선 순위 큐이다.
  (내가 원하는 순위가 맨앞으로 해결 할 수 있는 구조)
• max heap : 부모 노드의 키 >= 자식 노드 키
• min heap : 부모 노드의 키 <= 자식 노드 키
• heap 의 삽입

배열로 짠 힙
int   insertChildNodeHP(heap* pheap, heapNode element)
{
    int index_child;

    if (!pheap)
        return (FALSE);
    pheap->currentElementCount++;
    if (pheap->currentElementCount == pheap->maxElementCount && resizing(pheap))
        return (FALSE);
    pheap->pRootNode[pheap->currentElementCount].data = element.data;
    index_child = pheap->currentElementCount;
    while (pheap->pRootNode[index_child].data \
    		>= pheap->pRootNode[(int)(index_child / 2)].data
            && index_child != 1)
    {
        swap_node(pheap, index_child, (int)(index_child / 2));
        index_child = (int)(index_child / 2);
    }
    return (TRUE);
}

맨 뒤에 넣고 자식이 부모보다 크다면 스왑해준다.

• heap의 삭제

배열로 짠 힙
void        deleteheapNode(heap* pheap)
{
    int i;
    
    if (!pheap)
        return ;
    if (pheap->currentElementCount == 0)
        return ;
    pheap->pRootNode[1] = pheap->pRootNode[pheap->currentElementCount];
    i = 2;
    while (i <= pheap->currentElementCount)
    {
        if (i < pheap->currentElementCount && pheap->pRootNode[i].data < pheap->pRootNode[i + 1].data)
            i++;
        if (pheap->pRootNode[i].data < pheap->pRootNode[(int)(i / 2)].data)
            break ;
        else
            swap_node(pheap, i, (int)(i / 2));
        i *= 2;
    }
    pheap->currentElementCount--;
}

헤더 노드를 지우고 마지막 노드를 헤더 노드에 넣은 뒤 자식 노드와 비교해서 더 큰 자식 노드와 자리를 바꾼다. 자식 노드 보다 클 경우 중지