c++ - 访问数组之外​​的内存，二叉堆树

Question

对于一个类，我正在分配从命令行获取输入并使用输入创建堆树。从命令行读取数字。

例如:

示例输入:

./Heapify 2 9 7 6 5 8

示例输出:

9 6 8 2 5 7

我得到了这么多工作，似乎每个输入 6 个或更少的数字都可以正常工作。当输入是 7 个或更多这样的数字时:

示例输入:

./Heapify 3 10 8 7 5 9 6

我的输出:

32767 10 9 6 8 7 5

出了点问题。显然，我要么在我的程序中使用了很多内存并得到了一个“废话”数字，要么我正在访问我的数组之外的内存，这导致另一个“废话”数字。我一直在想可能出了什么问题，但我不确定。任何帮助，将不胜感激。

如果您有任何疑问或需要澄清，请随时提出。

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <fstream>
#include <iterator>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

void heap(int *array, int n);

int main(int argc, char* argv[]){

    int array[argc+1];
    int length = argc+1;

    for(int i = 1; i < length-1; i++){
        array[i]=atoi(argv[i]);
    }

    array[0]= -1;
    cout << "unheapified array: ";
    for(int k = 1; k < length-1; k++){
        cout << array[k] << " ";
    }
    cout << endl;
    heap(array, length);

    cout << "heapified array: ";
    for(int k = 1; k < length-1; k++){
        cout << array[k] << " ";
    }
    cout << endl;
return 0;
}

void heap(int *array, int n){
    int i, v, j,k;
    bool heap;

    for(int i=(n/2); i>0; --i){
        k = i;
        v = array[k];
        heap = false;

        while(heap == false && (2*k) <= n-1){
            j = 2*k;
            if(j<n){
                if(array[j] < array[j+1])
                    j += 1;
            }
            if (v >= array[j])
                heap = true;
            else{
                array[k] = array[j];
                k = j;
            }
        }       
        array[k] = v;   
    }
}

Answer 1

像这样修改你的 heap 函数:

    while(heap == false && (2*k) <= n-1){
        j = 2*k;
        if(j<n){
            assert((j+1)<n); // ADDED THIS
            if(array[j] < array[j+1])
                j += 1;
        }

您会看到 assert 被触发。所以 array[j+1] 不在最后。