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

我得到以下輸出：

堆具有元素... 110，100，80，70，90，40，10，50，30，60 ，20，

你看，數組沒有被排序。

它期待的結果進行排序像10, 20, 30, ...., 110,

我覈實了以下內容：

• ShiftDown()工作正常。
• Heapify()工作正常。

但HeapSort()函數不能排序數組。

任何人都可以請幫我找到這個bug嗎？它在我的邏輯或其他什麼？

#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. 在功能上堆排序你是第i個元素上調用IterativeShiftDown，而不是你需要，使其到達正確的位置，把它稱爲根元素。

2. 將根元素移動到上一個位置後，您不更新堆的大小。您需要知道，在您正在執行的堆排序中，我們將數組的一部分作爲堆，將其他部分作爲已排序部分。但是，你並沒有減小堆的大小，所以堆擴展到堆以外的排序區域，因此它再次選擇分類部分中的更大的元素，並導致再次形成堆。

替換隨您的堆排序功能，它會工作：

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