Minimum Binary Heap problem

[petra999]

Hello!
Using Cormen's "Introduction to Alogrithms" I modifed Max Binary Heap and created implementation of Minimum Binary Heap. But somewhere something goes wrong becouse program after compilation start to crash. If anyone find mistake, please tell me.
Thanks alot for any help.

File Heap.h:

#ifndef __HEAP_H__
#define __HEAP_H__

class Heap
{
    public:
        int *HeapArray;
        int size;

        Heap();
        ~Heap();

        int Parent(int);
        int Left(int);
        int Right(int);
        void SetSize(int);
        void MinHeapify(int);
        void BuildMinHeap();
        void HeapSort();
        int HeapMinimum();
        int HeapExtractMin();
        void HeapIncreaseKey(int, int);
        void MinHeapInsert(int);
        void Show();
};

#endif

File Heap.cpp:

#include "Heap.h"
#include <iostream>

Heap::Heap()
{
    this->HeapArray = (int*)malloc(1*sizeof(int));
}

Heap::~Heap()
{
    free(HeapArray);
}

int Heap::Parent(int i)
{
    return i/2;
}

int Heap::Left(int i)
{
    return 2*i;
}

int Heap::Right(int i)
{
    return 2*i+1;
}

void Heap::SetSize(int i)
{
    realloc(this->HeapArray, i*sizeof(int));
}

void Heap::MinHeapify(int i)
{
    int l = Left(i);
    int r = Right(i);
    int minimum;
    if(l < size && this->HeapArray[l] < this->HeapArray[i])
    {
        minimum = l;
    }
    else
    {
        minimum = i;
    }

    if(r < size && this->HeapArray[r] < this->HeapArray[minimum])
    {
        minimum = r;
    }

    if(minimum != i)
    {
        std::swap(this->HeapArray[i], this->HeapArray[minimum]);
        MinHeapify(minimum);
    }
}

void Heap::BuildMinHeap()
{
    for(int i = this->size/2; i >= 0; i--)
    {
        this->MinHeapify(i);
    }
}

int Heap::HeapMinimum()
{
    return this->HeapArray[0];
}

int Heap::HeapExtractMin()
{
    int min = this->HeapArray[0];
    this->HeapArray[0] = this->HeapArray[size-1];
    this->SetSize(this->size-1);
    this->MinHeapify(0);
    return min;
}

void Heap::HeapIncreaseKey(int i, int key)
{
    this->HeapArray[i] = key;
    while(i > 0 && this->HeapArray[Parent(i)] > this->HeapArray[i])
    {
        std::swap(this->HeapArray[Parent(i)], this->HeapArray[i]);
        i = Parent(i);
    }
}

void Heap::MinHeapInsert(int key)
{
    this->SetSize(this->size+1);
    this->HeapArray[size-1] |= this->HeapArray[size-1];
    this->HeapIncreaseKey(size-1, key);
}

void Heap::Show()
{
    for(int i = 0; i < this->size; i++)
    {
        std::cout << HeapArray[i] << std::endl;
    }
}

[helios]

Heap::size never seems to change. Also, this call: this->SetSize(this->size-1); has a chance to cause a segmentation fault.

[jsmith]

Just at first glance the class member size is used but never initialized.

[petra999]

Yes, that one of mistake, thanks for help!

But i still have problem.

Here, modifed Heap.cpp file:

#include "Heap.h"
#include <iostream>

Heap::Heap()
{
    this->HeapArray = (int*)malloc(0*sizeof(int));
    size = 0;
}

Heap::~Heap()
{
    free(HeapArray);
}

int Heap::Parent(int i)
{
    return i/2;
}

int Heap::Left(int i)
{
    return 2*i;
}

int Heap::Right(int i)
{
    return 2*i+1;
}

void Heap::SetSize(int i)
{
    realloc(this->HeapArray, i*sizeof(int));
    this->size = i;
}

void Heap::MinHeapify(int i)
{
    int l = Left(i);
    int r = Right(i);
    int minimum;
    if(l < size && this->HeapArray[l] < this->HeapArray[i])
    {
        minimum = l;
    }
    else
    {
        minimum = i;
    }

    if(r < size && this->HeapArray[r] < this->HeapArray[minimum])
    {
        minimum = r;
    }

    if(minimum != i)
    {
        std::swap(this->HeapArray[i], this->HeapArray[minimum]);
        MinHeapify(minimum);
    }
}

void Heap::BuildMinHeap()
{
    for(int i = this->size/2; i >= 0; i--)
    {
        this->MinHeapify(i);
    }
}

int Heap::HeapMinimum()
{
    return this->HeapArray[0];
}

int Heap::HeapExtractMin()
{
    int min = this->HeapArray[0];
    this->HeapArray[0] = this->HeapArray[size-1];
    this->SetSize(this->size-1);
    this->MinHeapify(0);
    return min;
}

void Heap::HeapIncreaseKey(int i, int key)
{
    this->HeapArray[i] = key;
    while(i > 0 && this->HeapArray[Parent(i)] > this->HeapArray[i])
    {
        std::swap(this->HeapArray[Parent(i)], this->HeapArray[i]);
        i = Parent(i);
    }
}

void Heap::MinHeapInsert(int key)
{
    this->SetSize(this->size+1);
    this->HeapArray[size-1] |= this->HeapArray[size-1];
    this->HeapIncreaseKey(size-1, key);
}

void Heap::Show()
{
    for(int i = 0; i < this->size; i++)
    {
        std::cout << HeapArray[i] << std::endl;
    }
}

Here is main:

#include <iostream>
#include "Heap.h"

int main()
{
    Heap MinHeap;
    MinHeap.MinHeapInsert(0);
    MinHeap.MinHeapInsert(23);
    MinHeap.MinHeapInsert(56);
    MinHeap.MinHeapInsert(90);
    MinHeap.Show();
    return 0;
}

But output is:
4079128
23
56
90.

I can't find the bug, i think problem as earlier is size.

Anyway THANK YOU FOR HELP

[helios]

Line 97: this->HeapArray[size-1] |= this->HeapArray[size-1]; What?

Okay, I understand what this whole thing is supposed to be, now.
Why don't you need to specify the parent when you insert a new node?

[petra999]

Ok. Line 97 is unneeded i think, I don't know why write this, i found it when I was reading Cormen's book, but i think is unnesesary.