由于某种原因,我的堆没有正常工作。使用以下测试程序:
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()
函数无法对数组进行排序。有人能帮我找到虫子吗?这是我的逻辑还是别的?
#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);
}
}
最佳答案
我研究了代码,发现了一些错误。您正确地创建了堆,但是在排序时,您犯了一些错误:
在函数HeapSort中,您要在第i个元素上调用IterativeShiftDown,而需要在根元素上调用它,以便它到达正确的位置。
同样,在将根元素移动到最后一个位置之后,您不会更新堆的大小。您需要知道,在堆排序中,我们将数组的一部分作为堆,另一部分作为排序部分。但您并没有减小堆的大小,因此堆会超出堆扩展到排序区域,因此它会再次选择排序部分中的较大元素,并再次导致堆的形成。
将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;
}