时间戳

首页 > 解决方案 > 给定一个整数数组，需要在 Max_Heap 上运行操作。收到错误“分段错误”，有什么想法吗？(C++)

c++ - 给定一个整数数组，需要在 Max_Heap 上运行操作。收到错误“分段错误”，有什么想法吗？(C++)

问题描述

这是我在这里的第一篇文章，所以请多多包涵。我正在处理一项任务，并查看了各种资源来创建和解决这个问题。

提示问题 我已经编写了 max_heapify、print、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;


     }

标签： c++arraysprintingswapmax-heap

解决方案

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

您的代码中有两个问题：

问题一：

在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这样，递归调用将在位置处堆积数组元素。

推荐阅读