C언어 Heap관련 질문입니다.


typedef struct HeapElement
{
    DSKEY  heKey;
    void *  heData;
} HeapElement;

struct Heap
{
    int         hpMode; /* Minimize or Maximize */
    int         hpSize;
    int        hpFilled;
    int        hpGrowBy;
    HeapElement**  hpArray;
    HEAPCMPFUNC    hpCmpFunc;
    HEAPCHGFUNC    hpChgFunc;   // *(void*, jnt)
};

heapInsert(HEAP heap,const DSKEY key,void *data)
{
    Heap    *   h = (Heap*)heap;
    HeapElement *   he;
    int         i, pidx;
    HeapInternCmp   cmp_func;

    //맥스힙, 민힙 중 설정
    if (h->hpMode == HEAP_MINIMIZE)
        cmp_func = heap_larger;
    else 
        cmp_func = heap_smaller;

    /* 1. Make a new element */
    he = heap_new_element(key,data);

    /* 2. Grow the heap if needed */

    if (NEEDS2GROW(h) && heap_grow(h))

    /* 3. Insert the new element into the heap */

    i = HSIZE(h);
    pidx = HPARENT(i);
    printf("i: %d pidx: %d\n",  i, pidx);
    int pdd;
    int hed;
    if(pidx >= 0)
    {
        pdd = *(int*)HARRAY(h, pidx)->heKey;
        hed = *(int*)he->heKey;

        printf("pidx: %d, he: %d\n", pdd, hed);
    }

    while (i > 0 && cmp_func(h,HARRAY(h,pidx),he))
    {
        int t = pidx;
        HARRAY(h, pidx) = HARRAY(h, i);
        HARRAY(h,i) = HARRAY(h, t) ;

        i = pidx;
        pidx = HPARENT(i);
    }

console

Heap관련 과제 중 질문드립니다. 코드는 새로운 key와 data를 힙에 삽입하는 ADT구요. main에서 반복적으로 실행합니다.(KEY랑 DATA랑 같은 것으로 취급합니다.) 질문드리고 싶은것은 콘솔화면을 보시면 아시겠지만 분명 0번 힙에 첫 인풋값인 14를 저장했는데, 어찌된일인지 그 다음 콜에서는 0번자리 값이 14가 아닌 그다음 인풋인 25로 저장이 되어 있네요.... 추측해보건데 참조문제 인 것 같은데, 도저히 어떻게 고쳐야할지 감이 안잡힙니다...ㅠㅠ


조회수 270


2 답변


max 힙이라면 14 -> 25 순서로 입력했을 시 최상위 요소가 25로 변경되어 있는 게 정상 동작입니다.

코드로 옮기시기 전에 트리에 자료가 어떻게 입력되고 삭제되는지 손으로 먼저 그려보시는 게 많은 도움이 됩니다.

힙 트리 동작

  • 2016년 05월 04일에 작성됨
    프로그래밍 언어를 좋아하는 프로그래머

  • 네 근데... 문제는 그게 힙 특성과 상관 없이 그냥 뒤에 들어온 값이 앞에 인덱스에도 들어가서 결국 마지막 값으로 전체 힙 배열 값이 같아지더라구요... 1, 2, 3, 4, 5 가 입력되면 {5, 5, 5, 5, 5} 이런식으로,,,    YunseobShin   2016.5.5 12:54     
  • 그럼 문제가 있는게 맞네요 ㅜㅜ 컴파일 되는 형태로 올려주시면 다시 한번 확인해 보겠습니다.    정대원   2016.5.5 21:19     

HeapInsesrt 의 끝부분에서 swap이 잘못되었습니다.

    while (i > 0 && cmp_func(h,HARRAY(h,pidx),he))
    {
        int t = pidx; // t와  pidx 가 같음으로 임시로 저장할 공간이 없네요.
        HARRAY(h, pidx) = HARRAY(h, i);
        HARRAY(h,i) = HARRAY(h, t) ;

        i = pidx;
        pidx = HPARENT(i);
    }

다음과 비슷하게 수정해야 할 것 같습니다.

    while (i > 0 && cmp_func(h,HARRAY(h,pidx),he))
    {
        HeapElement t; // HARRAY 가 반환하는것이 HeapElement 라면..
        // 혹은 Heap의 빈 공간이 있다면 그 공간을 이용해도 되겠습니다.
        t = HARRAY(h, pidx);
        HARRAY(h, pidx) = HARRAY(h, i);
        HARRAY(h,i) = t

        i = pidx;
        pidx = HPARENT(i);
    }
  • 2016년 05월 08일에 작성됨
    리눅스(유닉스) 기반의 시스템에서 웹 서비스를 개발하고 있습니다.

로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close