给定一个整数数组，需要在Max_Heap上运行操作。得到错误"segmentation fault"，有什么想法吗？(C++)

Question

这是我在这里的第一篇文章，所以请耐心等待。 我正在做一项任务，并查看了各种来源来创建和解决这个问题。

提示问题 我已经编写了max_heapify、打印、build_heap和delete_root函数，但我唯一得到的输出是退出，分段错误我通过同一个编译器运行了类似的代码，没有任何问题。

我意识到我的代码没有完全缩进，但如果有人对如何进行此运行有任何建议，将不胜感激。

#include <iostream>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;

void max_heapify(int arr[], int n, int i){
int max_val = i;
int left = 2*i +1;
int right = 2*i +2;
// if left child is larger than root 
// set  root equal to left child
if ( left < n && arr[left] > arr[max_val] )
max_val = left;
// if right child is larger than largest 
if (right < n && arr[right] > max_val)
max_val = right;
// if largest is not root
if (max_val != i)
{
//swap values
int temp = arr[i];
arr[i] = arr[max_val];
arr[max_val] = temp;
max_heapify(arr,n,i);
}
}
void buildh(int arr[],int n)
{
//index of last non leaf node
int indx = (n/2) -1;
for (int i = indx; i >= 0; i--)
{
max_heapify(arr,n,i);
}
}
void printh(int arr[], int n) 
{ 
cout << "Heap is:n"; 
for (int i = 0; i < n; ++i) 
cout << arr[i] << " "; 
cout << "n"; 
} 
void delete_root(int arr[], int n)
{
int last = arr[n-1];
arr[0] = last;
n = n-1;
max_heapify(arr,n,0);
}

int main() {
int arr[] = {28,12,17,5,7,22,13,12,4,11,16}; // create an array of values
int n = sizeof(arr) / sizeof(arr[0]); 
buildh(arr,n);
printh(arr,n);
delete_root(arr,n);
return 0;

}

Answer 1

由于max_heapify()继续递归调用自己而未达到终止条件而发生的段错误。

代码中的两个问题：

问题1：

在max_heapify()，在这个声明中

if (right < n && arr[right] > max_val)

应该是arr[max_val].正确的陈述将是

if (right < n && arr[right] > arr[max_val])

问题2：

在每次调用max_heapify()时，您都在^i位置堆积元素

max_heapify(arr,n,i);
^^

相反，您应该在索引max_val识别出left和right子级之间的最大值并交换a[i]值和a[max_val]值后传递索引

max_heapify(arr,n,max_val);

这样，递归调用将在max_val位置堆积数组元素。

Answer 2

我认为问题发生在这个函数中：

void max_heapify(int arr[], int n, int i){
int max_val = i;
int left = 2*i +1;
int right = 2*i +2;
// if left child is larger than root, set root equal to left child
if ( left < n && arr[left] > arr[max_val] )
max_val = left;
// if right child is larger than largest 
if (right < n && arr[right] > max_val)
max_val = right;
// if largest is not root
if (max_val != i){
//swap values
int temp = arr[i];
arr[i] = arr[max_val];
arr[max_val] = temp;
max_heapify(arr,n,i);
}
}

最后，你称max_heapify()在它本身。此代码的问题在于递归没有终止条件;换句话说，没有什么可以阻止它递归到无穷大。正如@Retired Ninja评论的那样，此过程可能是导致Segmentation Fault的原因，因为它超过了允许的最大递归深度。

要解决此问题，您需要考虑减少max_heapify()递归深度的方法(您真的需要递归调用它吗？