c - 我的 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 has Elements...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. 在函数 HeapSort 中，您在第 i 个元素上调用 IterativeShiftDown，而不是在根元素上调用它，以便它到达正确的位置。

2. 此外，在将根元素移动到最后一个位置后，您并没有更新堆的大小。您需要知道，在您正在执行的堆排序中，我们将数组的一部分作为堆，另一部分作为排序部分。但是您并没有减小堆的大小，因此堆延伸到堆之外到已排序区域，因此它再次选择已排序部分中的较大元素并导致再次形成堆。

将您的 HeapSort 函数替换为它会起作用:

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