한빛미디어

Heap을 공부하다가, DeleteMin함수를 보면서 왜 2개의 Input (Heap* H, HeapNode* Root)이 필요한지 생각해봤습니다.

Root은 dummy node, 즉 실질적으로 꼭 필요하지는 안은데 함수를 원활히 돌릴려고 만든 거라고 생각이 들었습니다.
그래서 DeleteMin(Heap* H) 함수를 만들어봤어요.
성능이 더 났다는건 아니고요, 그냥 dummy node를 생성해서 집어넣을 필요가 없어졌다는 거죠. ㅋ

역시나 또 첨부파일이 안 되네요 -_-.. 밑에 함수 붙여넣기 했어요.

제가 유학생이라 주석을 영어로 달았어요. 양해 바람...

그리고 혼자 공부하는거보다 의견공유 하는게 좋을 꺼 같아서 카페 만들었어요.
http://cafe.naver.com/algorithmkorea

혹시 저 처럼 혼자서 공부하시는 분들 의견 공유도 할 겸 들러주세요.. 저자님도 들러주시면 감사... ㅋ

//Deletes the node who has the minimum data value, which is root
void      HEAP_DeleteMin( Heap* H)
{
    //Heap is empty
    if(H->UsedSize == 0) return;
    
    //We empty the Heap
    if(H->UsedSize == 1)
    {
        memset(&(H->Nodes[0]), 0, sizeof(HeapNode)); //delete root
        H->UsedSize--;
        return;
    }
    
    HEAP_SwapNodes(H, 0, H->UsedSize - 1);
    memset(&(H->Nodes[H->UsedSize - 1]), 0, sizeof(HeapNode));
    
    //Reorganize Heap
    //First step : move the deepest node to the root location
    
    /* Second step:
       Compare left child node and right child node, and
       switch the new root with whichever is samller.
       Keep doing this until either it becomes a leaf
       or both of its children are bigger than it.
    */
    int New = 0;
    int Left = HEAP_GetLeftChild(0);
    int Right = Left + 1;
    int NewVal = H->Nodes[0].Data;
    HeapNode LeftChild = H->Nodes[Left];
    HeapNode RightChild = H->Nodes[Right];
  
    while(HEAP_GetLeftChild(New) < H->UsedSize - 1)
    {
        int LeftVal = LeftChild.Data;
        int RightVal = RightChild.Data;
        
        if(Left == H->UsedSize - 2) //Left is the only child
        {
            if(LeftVal >= NewVal) break;
            else
            {
                HEAP_SwapNodes(H, New, Left);
                break;
            }
        }
                
        //Both children are bigger than the new root
        if(LeftVal >= NewVal && RightVal >= NewVal) return;
        
        if(LeftVal < RightVal)
        {
            HEAP_SwapNodes(H, Left, New);
            New = Left;
        }
        else
        {
            HEAP_SwapNodes(H, Right, New);
            New = Right;
        }
        
         Left = HEAP_GetLeftChild(New);
         Right = Left + 1;
         LeftChild = H->Nodes[Left];
         RightChild = H->Nodes[Right];
    }
          
    H->UsedSize--; //Deletion is officially done

    //Shrink the heap if it is half empty
    if (H->UsedSize < (H->Capacity / 2))
    {
        H->Capacity /= 2;
        H->Nodes = (HeapNode*)realloc(H->Nodes, sizeof(HeapNode) * H->Capacity);
    }
}