내 Heaport에 문제가 있습니까?

Question

내 Heaport가 올바르게 작동하지 않습니다. I는 다음과 같은 결과를 얻을

int main() 
{ 
    AddArrayElement(10); 
    AddArrayElement(110); 
    AddArrayElement(20); 
    AddArrayElement(100); 
    AddArrayElement(30); 
    AddArrayElement(90); 
    AddArrayElement(40); 
    AddArrayElement(80); 
    AddArrayElement(50); 
    AddArrayElement(70); 
    AddArrayElement(60); 

    HeapSort(); 
    PrintHeap(); 

    system("pause"); 
    return 0; 
} 

: 다음의 시험 프로그램을 사용

힙 요소 ... 110, 100, 80, 70, 90, 40, 10, 50, 30, 60을 갖는 , 20,

배열이 정렬되지 않습니다.

• ShiftDown()가 제대로 작동 : 그것은 결과를 기다리고 있었다
  이

  10, 20, 30, ...., 110,

  처럼 정렬 할 나는 다음 확인했습니다.

• Heapify()이 올바르게 작동하고 있습니다.

그러나 HeapSort() 함수는 배열을 정렬 할 수 없습니다.

누구든지 버그를 찾도록 도와 줄 수 있습니까? 그것은 내 논리 또는 다른 것입니까?

#include "Heap.h" 
#include <stdio.h> 
#include <math.h> 

int array[SIZE] = {0}; 
int lastElementIndex = -1; 

void PrintHeap() 
{ 
    int i=0; 

    printf("\n\n"); 

    if(lastElementIndex >= 0) 
    { 
     printf("Heap has Elements..."); 

     for(i=0 ; i<=lastElementIndex ; i++) 
     { 
      printf("%d, ", array[i]); 
     } 
    } 
    else 
    { 
     printf("Heap is Empty..."); 
    } 

    printf("\n\n"); 
} 

void Swap(int *a, int *b) 
{ 
    int temp = *a; 
    *a = *b; 
    *b = temp; 
} 

void SwapElements(int i, int j) 
{ 
    Swap(&array[i], &array[j]); 
} 

void SetRootElement(int element) 
{ 
    array[0] = element; 
} 

void DeleteRightMostElement() 
{ 
    array[lastElementIndex] = EMPTY; 

    --lastElementIndex; 
} 

void AddArrayElement(int element) 
{ 
    ++lastElementIndex; 

    array[lastElementIndex] = element; 
} 

#pragma region HasXXX() 
int HasAnyElement() 
{ 
    if(lastElementIndex > -1) return 1; 
    else return 0; 
} 

int HasLeftChild(int i) 
{ 
    int lastIndex = EMPTY; 

    if(HasAnyElement()) 
    { 
     lastIndex = GetLastElementIndex(); 

     if(lastIndex<=0 || lastIndex==i) 
     {   
      return 0; 
     } 
     else 
     { 
      if(2*i+1 <= GetLastElementIndex()) return 1; 
      else return 0; 
     } 
    } 
    else 
    { 
     return 0; 
    } 
} 

int HasRightChild(int i) 
{ 
    int leftChildIndex = EMPTY; 
    int rightChildIndex = EMPTY; 

    if(HasAnyElement()) 
    { 
     if(HasLeftChild(i)) 
     {   
      leftChildIndex = GetLeftChildIndex(i); 
      rightChildIndex = leftChildIndex + 1; 

      if(rightChildIndex <= GetLastElementIndex()) 
      { 
       return 1; 
      } 
      else 
      { 
       if(2*i+2 <= GetLastElementIndex()) return 1; 
       else return 0; 
      } 
     } 
     else 
     { 
      return 0; 
     } 
    } 
    else 
    { 
     return 0; 
    } 
} 

int HasAnyChild(int i) 
{ 
    if(HasLeftChild(i) || HasRightChild(i)) return 1; 
    else return 0; 
} 

int HasBothChild(int i) 
{ 
    int hasLeftChild = HasLeftChild(i); 
    int hasRightChild = HasRightChild(i); 

    if(hasLeftChild && hasRightChild) return 1; 
    else return 0; 
} 

int HasParent(int i) 
{ 
    if(i>0) return 1; 
    else return 0; 
} 
#pragma endregion 

#pragma region GetXXXIndex() 
int GetElementsCount() 
{ 
    if(HasAnyElement()) return lastElementIndex + 1; 
    else return EMPTY; 
} 
int GetLastElementIndex() 
{ 
    if(HasAnyElement()) return lastElementIndex; 
    else return EMPTY; 
} 

int GetParentIndex(int i) 
{ 
    if(HasParent(i)) return (int)floor((i-1)/2); 
    else return EMPTY; 
} 

int GetLeftChildIndex(int i) 
{ 
    if(HasLeftChild(i)) return (2*i + 1); 
    else return EMPTY; 
} 

int GetRightChildIndex(int i) 
{ 
    if(HasRightChild(i)) return (2*i + 2); 
    else return EMPTY; 
} 
#pragma endregion 

#pragma region GetXXXElement() 
int GetRootElement() 
{ 
    return array[0]; 
} 

int GetRightMostElement() 
{ 
    if(HasAnyElement()) return array[lastElementIndex]; 
    else return EMPTY; 
} 

int GetElement(int i) 
{ 
    if(HasAnyElement()) return array[i]; 
    else return EMPTY; 
} 

int GetParentElement(int i) 
{ 
    if(HasParent(i)) return array[GetParentIndex(i)]; 
    else return EMPTY; 
} 

int GetLeftChildElement(int i) 
{ 
    if(HasLeftChild(i)) return array[GetLeftChildIndex(i)]; 
    else return EMPTY; 
} 

int GetRightChildElement(int i) 
{ 
    if(HasRightChild(i)) return array[GetRightChildIndex(i)]; 
    else return EMPTY; 
} 
#pragma endregion 

#pragma region RemoveElementFromHeap() 
void IterativeShiftDown(int i) 
{ 
    int leftOrRightChildIndex = EMPTY; 
    int currentIndex = i; 
    int currentElement = EMPTY; 
    int childElement = EMPTY; 

    while(HasAnyChild(currentIndex)) 
    { 
     if(HasBothChild(currentIndex)) 
     { 
      if(GetLeftChildElement(currentIndex) > GetRightChildElement(currentIndex)) 
      { 
       leftOrRightChildIndex = GetLeftChildIndex(currentIndex); 
      } 
      else 
      { 
       leftOrRightChildIndex = GetRightChildIndex(currentIndex); 
      } 
     } 
     else if(HasLeftChild(currentIndex)) 
     { 
      leftOrRightChildIndex = GetLeftChildIndex(currentIndex); 
     } 

     currentElement = GetElement(currentIndex); 
     childElement = GetElement(leftOrRightChildIndex); 

     if(currentElement < childElement) 
     { 
      SwapElements(currentIndex, leftOrRightChildIndex); 
     } 

     currentIndex = leftOrRightChildIndex; 
    } 
} 

void ShiftDownTheRootElement() 
{ 
    IterativeShiftDown(0); 
} 
#pragma endregion 

void Heapify() 
{ 
    int i = 0; 

    int count = GetElementsCount(); 

    int half = (count-2)/2; 

    for(i=half ; i>=0 ; i--) 
    { 
     IterativeShiftDown(i); 
    } 
} 

void HeapSort() 
{ 
    int i = 0; 
    Heapify(); 

    for (i=GetLastElementIndex() ; i>=0 ; i--) 
    { 
     SwapElements(i, 0); 

     IterativeShiftDown(i); 
    } 
} 

Answer 1

나는 코드를 연구하고 실수를 발견했다. 당신은 제대로 힙을 만드는하지만 정렬하는 동안 당신은 몇 가지 실수를했을 : 당신은 i 번째 요소에 IterativeShiftDown 호출 힙 정렬 기능에

1. 대신에 당신이 올바른 위치에 도달 할 수 있도록 루트 요소를 호출 할 필요를 .

2. 또한 루트 요소를 마지막 위치로 이동 한 후에는 힙 크기를 업데이트하지 않습니다. 배열에서 힙 (heap) 배열의 일부분과 정렬 된 부분 (sorted part)을 가지고 있다는 것을 알아야합니다. 그러나 힙 크기를 줄이지 않고 힙을 넘어 힙을 정렬 된 영역으로 확장하므로 정렬 된 부분에있는 더 큰 요소를 다시 선택하여 힙을 다시 형성합니다.

이와 힙 정렬 기능이 작동 바꾸기 :

void HeapSort() 
{ 
    int i = 0; 
    Heapify(); 

    int size=GetLastElementIndex(); 

    for (i=size ; i>=0 ; i--) 
    { 
     SwapElements(i, 0); 
     lastElementIndex--; 

     IterativeShiftDown(0); //shift the root down 
    } 

    lastElementIndex=size; 
}