Minimum Binary Heap problem

May 5, 2009 at 10:09am
petra999 (3)
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
#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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
#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;
    }
}
May 5, 2009 at 12:09pm
helios (17607)
Heap::size never seems to change. Also, this call: this->SetSize(this->size-1); has a chance to cause a segmentation fault.
May 5, 2009 at 12:09pm
jsmith (5804)
Just at first glance the class member size is used but never initialized.
May 5, 2009 at 1:57pm
petra999 (3)
Yes, that one of mistake, thanks for help!

But i still have problem.

Here, modifed Heap.cpp file:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
#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:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
#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;
}
Edit & run on cpp.sh


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
May 5, 2009 at 3:21pm
helios (17607)
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?
May 5, 2009 at 4:52pm
petra999 (3)
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.

Topic archived. No new replies allowed.