Algorithm that builds heap

Question

I am trying to implement build_max_heap function that creates the heap( as it is written in Cormen's "introduction do algorithms" ). But I am getting strange error and i could not localize it. My program successfully give random numbers to table, show them but after build_max_heap() I am getting strange numbers, that are probably because somewhere my program reached something out of the table, but I can not find this error. I will be glad for any help.

For example I get the table:

0 13 18 0 22 15 24 19 5 23

And my output is:

24 7 5844920 5 22 15 18 19 0 23

My code:

#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

In case you're still having problems, below is my own implementation that you might use for reference. It was also based on Cormen et al. book, so it's using more or less the same terminology. It may have arbitrary types for the actual container, the comparison and the swap functions. It provides a public queue-like interface, including key incrementing.

Because it's part of a larger software collection, it's using a few entities that are not defined here, but I hope the algorithms are still clear. CHECK is only an assertion mechanism, you can ignore it. You may also ignore the swap member and just use std::swap.

Some parts of the code are using 1-based offsets, others 0-based, and conversion is necessary. The comments above each method indicate this.

template <
    typename T,
    typename ARRAY = array <T>,
    typename COMP = fun::lt,
    typename SWAP = fun::swap
>
class binary_heap_base
{
protected:

    ARRAY a;
    size_t heap_size;

    SWAP swap_def;
    SWAP* swap;

    // 1-based
    size_t parent(const size_t n) { return n / 2; }
    size_t left  (const size_t n) { return n * 2; }
    size_t right (const size_t n) { return n * 2 + 1; }

    // 1-based
    void heapify(const size_t n = 1)
    {
        T& x = a[n - 1];
        size_t l = left(n);
        size_t r = right(n);
        size_t select =
            (l <= heap_size && COMP()(x, a[l - 1])) ?
            l : n;
        if (r <= heap_size && COMP()(a[select - 1], a[r - 1]))
            select = r;
        if (select != n)
        {
            (*swap)(x, a[select - 1]);
            heapify(select);
        }
    }

    // 1-based
    void build()
    {
        heap_size = a.length();
        for (size_t n = heap_size / 2; n > 0; n--)
            heapify(n);
    }

    // 1-based
    size_t advance(const size_t k)
    {
        size_t n = k;
        while (n > 1)
        {
            size_t pn = parent(n);
            T& p = a[pn - 1];
            T& x = a[n - 1];
            if (!COMP()(p, x)) break;
            (*swap)(p, x);
            n = pn;
        }
        return n;
    }

public:

    binary_heap_base() { init(); set_swap(); }
    binary_heap_base(SWAP& s) { init(); set_swap(s); }

    binary_heap_base(const ARRAY& a) { init(a); set_swap(); }
    binary_heap_base(const ARRAY& a, SWAP& s) { init(a); set_swap(s); }

    void init() { a.init(); build(); }
    void init(const ARRAY& a) { this->a = a; build(); }

    void set_swap() { swap = &swap_def; }
    void set_swap(SWAP& s) { swap = &s; }

    bool empty() { return heap_size == 0; }

    size_t size() { return heap_size; }

    size_t length() { return heap_size; }

    void reserve(const size_t len) { a.reserve(len); }

    const T& top()
    {
        CHECK (heap_size != 0, eshape());
        return a[0];
    }

    T pop()
    {
        CHECK (heap_size != 0, eshape());
        T x = a[0];
        (*swap)(a[0], a[heap_size - 1]);
        heap_size--;
        heapify();
        return x;
    }

    // 0-based
    size_t up(size_t n, const T& x)
    {
        CHECK (n < heap_size, erange());
        CHECK (!COMP()(x, a[n]), ecomp());
        a[n] = x;
        return advance(n + 1) - 1;
    }

    // 0-based
    size_t push(const T& x)
    {
        if (heap_size == a.length())
            a.push_back(x);
        else
            a[heap_size] = x;
        return advance(++heap_size) - 1;
    }

};

Answer 2

Indeed, the table is accessed with out-of-bounds indexes.

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

I think you meant && in this condition.

The same for the next branch with r.