回复小老帖子，觉得我的小贡献可能会对未来的访客有所帮助。
如果我错过了任何场景，请专家验证并纠正我的逻辑。
考虑了强旭链接和基于零的索引逻辑。这是 C# 代码，并使用以下输入进行了测试。
//------------------------------------------------ -------------------------------------------------- ---------------------------------------------
// 输入数组：
int[] ErrCaseArry = new int[] { 66, 4, 23, 4, 78, 6, 44, 11, 22, 1, 99};
int[] GenCaseArry = new int[] { 30, 20, 40, 10, 90, 160, 140, 100, 80, 70 };
int[] NearlySortedArry = new int[] { 1, 2, 3, 4, 6, 5 };
int[] FewSortedArry1 = new int[] { 3, 2, 1, 4, 5, 6 };
int[] FewSortedArry2 = new int[] { 6, 2, 3, 1, 5, 4 };
int[] ReversedArry1 = new int[] { 6, 5, 4, 3, 2, 1 };
int[] FewDuplsArry2 = new int[] { 1, 3, 1, 2, 1, 3 };
int[] MoreDuplsArry3 = new int[] { 1, 1, 2, 2, 1, 2 };
//------------------------------------------------ -------------------------------------------------- ---------------------------------------------
public void HeapSort(int[] listToSort)
{
int LastChildIndex = listToSort.Length -1;
int parentElementIndex = ((LastChildIndex - 1)/ 2);
//1. Use this loop to Construct Heap Array (Max/Min) by using Heapify function on every node.
while (parentElementIndex >= 0) // (N - 1) / 2 to 0
{
Heapify(listToSort, parentElementIndex, LastChildIndex); // (N - 1) / 2 & Lenght - 1
parentElementIndex--;
}
//-----------------------------------------------------------------------------------------------------------------------------------------------
AppendArrayToResultString("Max Heap\t", listToSort);
//2. Heap sort algorithm takes largest element off the heap and places it at the end of an array.
// This phase continue until all the elements are placed in the array that are in sorted order.
int sortedElementIndex = listToSort.Length - 1;
//-----------------------------------------------------------------------------------------------------------------------------------------------
// In this loop get Largest Element to Zero'th postion and move to end. and reduce the loop count from Heapify Array. So that elements gets sorted from right.
while (sortedElementIndex >= 0) // (N - 1) to 1
{
// Swap the elements (root(maximum value)) of the heap with the last element of the heap
Swap(ref listToSort[0], ref listToSort[sortedElementIndex]);
// sortedElementIndex-- : Decrease the size of the heap by one so that the previous max value will stay in its proper placement
sortedElementIndex--;
if (sortedElementIndex == -1) break;
// Since largest elemented from 0 to last, Re Heapify and get the remaining largest element and place it in 0 position.
Heapify(listToSort, 0, (sortedElementIndex)); // 0 to (N - 1)
}
//-----------------------------------------------------------------------------------------------------------------------------------------------
}
//Heapify() function maintain the heap property (Max Heap or Min Heap). Can be recursive or can use iteration loop like while/for.
void Heapify(int[] listToSort, int parentIndext, int lastChildIndext)
{
//bool doneFlag = false;
int largestElementIndex = 0;
int leftChildIndex = parentIndext * 2 + 1;
int rightChildIndex = parentIndext * 2 + 2;
while (leftChildIndex <= lastChildIndext) //&& !doneFlag)
{
// If leftChild is larger than rightChild or it is the last child and there is no rightChild for this parent.
// Then consider leftChild as largestElement else consider rightChild as largestElement.
if (leftChildIndex == lastChildIndext || listToSort[leftChildIndex] > listToSort[rightChildIndex])
{
largestElementIndex = leftChildIndex;
}
else
{
largestElementIndex = rightChildIndex;
}
//-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
// If largestElement is larger than parent then swap them and make parent as largestElement to continue the loop.
if (listToSort[parentIndext] < listToSort[largestElementIndex])
{
// Make largestElement as parent. And continue finding if childs (left and right) are bigger than element in largestIndex position.
Swap(ref listToSort[parentIndext], ref listToSort[largestElementIndex]);
// Repeat to continue sifting down the child now
parentIndext = largestElementIndex;
leftChildIndex = ((parentIndext * 2) + 1);
rightChildIndex = ((parentIndext * 2) + 2);
}
else
{
//doneFlag = true;
break; // Trying to avoid extra flag condition check. Or return.
}
}
}
//-----------------------------------------------------------------------------------------------------------------------------------------------
void Swap(ref int num1, ref int num2)
{
int temp = num1;
num1 = num2;
num2 = temp;
}