Heapsort

[10oTURfi]

Code below implements heapsort. It does not give desired output tho. It sometimes crashes and sometimes gives partially-sorted array. What am I doing wrong?

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <utility>
#include <vector>
using namespace std;

template <class T>
class Heap
{
public:
    Heap(size_t Num) :
    HeapSize(0),
    A(Num)
    {
        for (size_t i = 0; i < Num; ++i)
            A[i] = rand() % 50;
    }

    size_t Parent(size_t i)
    {
        return i / 2;
    }

    size_t Left(size_t i)
    {
        return i * 2 + 1;
    }

    size_t Right(size_t i)
    {
        return i * 2 + 2;
    }

    void MaxHeapify(size_t i)
    {
        size_t l = Left(i);
        size_t r = Right(i);
        size_t largest;

        if (l < HeapSize && A[l] > A[i])
            largest = l;
        else
            largest = i;
        if (r < HeapSize && A[r] > A[largest])
            largest = r;
        if (largest != i)
        {
            std::swap(A[i], A[largest]);
            MaxHeapify(largest);
        }
    }
    
    void BuildMaxHeap()
    {
        HeapSize = A.size();
        for (size_t i = HeapSize / 2; i > 0; --i)
            MaxHeapify(i);
    }
    
    void HeapSort()
    {
        BuildMaxHeap();
        for (size_t i = HeapSize-1; i > 0; --i)
        {
            std::swap(A[0], A[i]);
            --HeapSize;
            MaxHeapify(0);
        }
    }
    
    void Print()
    {
        for (size_t i = 0; i < A.size(); ++i)
            std::cout << A[i] << " ";
        std::cout << std::endl;
    }
private:
    std::vector<T> A;
    size_t HeapSize;
};

int main()
{
    srand(time(0));
    
    Heap<int> H(6);
    H.Print();
    H.HeapSort();
    H.Print();
}

16 11 23 40 24 38
23 11 24 38 40 135137
*** glibc detected *** ./a.out: free(): invalid next size (fast): 0x00000000021d0010 ***
a.out: malloc.c:2451: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.
Aborted (core dumped)

$ ./a.out
12 41 18 29 38 20 28 33
18 0 20 28 29 33 38 41

^12 disappeared, 0 appeared(?)?

[ne555]

if (l <= HeapSize && A[l] > A[i])
`HeapSize' is out of bounds

[cire]

If we take:

HeapSize = A.size();

And put it next to:

if (l <= HeapSize && A[l] > A[i])

and

if (r <= HeapSize && A[r] > A[largest])

Does that suggest anything to you?

[10oTURfi]

I fixed out of bonds errors (edited first post), but now it doesn't seem to sort the array :/

krofna@krofna-desktop:~/Development/Algorithms$ ./a.out
4 3 25 28 29 15
3 15 25 28 29 4

[ne555]

You aren't `MaxHeapify()'-ing the root in `BuildMaxHeap()'