Что случилось с моим Heapsort?

Question

По какой-то причине мой Heapsort работает некорректно. С помощью следующей тестовой программы:

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; 
} 

я получаю следующий результат:

Heap имеет элементы ... 110, 100, 80, 70, 90, 40, 10, 50, 30, 60 , 20,

Вы видите, массив не сортируется.

Он ожидал, что результат будет отсортирован как 10, 20, 30, ...., 110,

Я проверил следующее:

• ShiftDown() работает правильно.
• 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

Я изучил код и нашел некоторые ошибки. Вы правильно создавать кучу, но при сортировке вы сделали несколько ошибок:

1. В функции пирамидальной сортировки вы вызываете IterativeShiftDown на i-ой элемент вместо этого вам нужно вызвать его на корневом элементе так, что он достигает правильное положение ,

2. Также после перемещения корневого элемента в последнее место вы не обновляете размер кучи. Вам нужно знать, что в сортировке кучи, которую вы делаете на месте, у нас есть одна часть массива как куча и другая часть как отсортированная часть. Но вы не уменьшаете размер кучи, поэтому куча выходит за пределы кучи в отсортированную область, поэтому она снова выбирает больший элемент, который находится в сортированной части, и снова приводит к образованию кучи.

Replace ваша функция пирамидальной сортировки с этим он будет работать:

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; 
}