我第一次尝试实现堆排序算法,但是 heapify 函数出现错误。
Unhandled exception at 0x0005369A in heapify.exe: Stack cookie instrumentation code detected a stack-based buffer overrun.
控制台确实打开了,输出是999 10 5 11 1012398875 2 0 1
.
有人可以帮我理解这里出了什么问题吗?谢谢你。
#include <iostream>
// given the address of element 0 of an array, and a non-zero index k, heapify assumes that the L/R subtrees
// of node k are max heaps. But the subtrees combined with node k do not necesarily form
// a max heap. heapify interchanges the value at node k with the value of one of its children,
// and then calls itself on the subtree in question
int heapify(int* n, int k, int sizeOfHeap)
{
// terminate the function if the input "node" is not actually a node
if (k > sizeOfHeap)
{
return 0;
}
int root = *(n + k); // value of kth node
int leftChild = *(n + 2 * k); // value of left chold
int rightChild = *(n + 2 * k + 1); // value of right child
if (root < leftChild)
{
// swap value of kth node with value of its left child
int temp = root;
*(n + k) = leftChild;
*(n + 2 * k) = root;
// call heapify on the left child
heapify(n, 2 * k, sizeOfHeap);
}
else
{
// swap value of kth node with value of its right child
int temp = root;
*(n + k) = rightChild;
*(n + 2 * k + 1) = root;
// call heapify on right child
heapify(n, 2 * k + 1, sizeOfHeap);
}
}
int main()
{
// arr is the array we will heapify. 999 is just a placeholder.
// The actual (almost) heap occupies indices 1 - 7
int arr[8] = {999, 3, 10, 11, 5, 2, 0, 1};
int sizeOfHeap = 8;
heapify(arr, 1, sizeOfHeap);
// print out arr
int i;
for (i = 0; i <= 7; i++)
{
std::cout << arr[i] << std::endl;
}
}