c++ - 建立堆的算法

Question

我正在尝试实现创建堆的 build_max_heap 函数(正如 Cormen 的“introduction do algorithms”中所写)。但是我遇到了奇怪的错误，我无法将其本地化。我的程序成功地为表提供了随机数，并显示了它们，但是在 build_max_heap() 之后我得到了奇怪的数字，这可能是因为我的程序在某处达到了表外的某些东西，但我找不到这个错误.我很乐意提供任何帮助。

例如我得到表格:

0 13 18 0 22 15 24 19 5 23

我的输出是:

24 7 5844920 5 22 15 18 19 0 23

我的代码:

#include <iostream>
#include <ctime>
#include <stdlib.h>  
const int n = 12; // the length of my table, i will onyl use indexes 1...n-1
struct heap
{
    int *tab;
    int heap_size;
};
void complete_with_random(heap &heap2)
{
    srand(time(NULL));
    for (int i = 1; i <= heap2.heap_size; i++)
    {
        heap2.tab[i] = rand() % 25;
    }
    heap2.tab[0] = 0;
}
void show(heap &heap2)
{
    for (int i = 1; i < heap2.heap_size; i++)
    {
        std::cout << heap2.tab[i] << " ";
    }
}
int parent(int i)
{
    return i / 2;
}
int left(int i)
{
    return 2 * i;
}
int right(int i)
{
    return 2 * i + 1;
}
void max_heapify(heap &heap2, int i)
{
    if (i >= heap2.heap_size || i == 0)
    {
        return;
    }
    int l = left(i);
    int r = right(i);
    int largest;
    if (l <= heap2.heap_size || heap2.tab[l] > heap2.tab[i])
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if (r <= heap2.heap_size || heap2.tab[r] > heap2.tab[i])
    {
        largest = r;
    }
    if (largest != i)
    {
        std::swap(heap2.tab[i], heap2.tab[largest]);
        max_heapify(heap2, largest);
    }
}
void build_max_heap(heap &heap2)
{
    for (int i = heap2.heap_size / 2; i >= 1; i--)
    {
        max_heapify(heap2, i);
    }
}
int main()
{
    heap heap1;
    heap1.tab = new int[n];
    heap1.heap_size = n - 1;
    complete_with_random(heap1);
    show(heap1);
    std::cout << std::endl;
    build_max_heap(heap1);
    show(heap1);
}

Answer 1

确实，使用越界索引访问该表。

if (l <= heap2.heap_size || heap2.tab[l] > heap2.tab[i])
                         ^^

我想你的意思是 && 在这种情况下。

与 r 的下一个分支相同。