-
April 19th, 2013, 02:24 PM
#1
Implementing a Heap
So I'm going through and trying to do a recursive implementation of a Heap. I keep getting access violations for some reason on my sifts (_siftUp) - even though I'm trying to insert into sub[0] (currSize = 0 in the constructor). I don't think either of my sifts are implemented correctly, are they?
Here's my Heap:
Code:
#ifndef HEAP_H
#define HEAP_H
//**************************************************************************
template<typename TYPE>
class Heap
{
private:
TYPE* heapData;
int currSize;
int capacity;
void _siftUp(int);
void _siftDown(int);
int _leftChildOf(int) const;
int _parentOf(int) const;
public:
Heap(int c = 100);
~Heap();
bool viewMax(TYPE&) const;
int getCapacity() const;
int getCurrSize() const;
bool insert(const TYPE&);
bool remove(TYPE&);
};
//**************************************************************************
template<typename TYPE>
Heap<TYPE>::Heap(int c = 100)
{
capacity = 100;
currSize = 0;
}
//**************************************************************************
template<typename TYPE>
Heap<TYPE>::~Heap()
{
delete heapData;
currSize = 0;
capacity = 0;
}
//**************************************************************************
template<typename TYPE>
bool Heap<TYPE>::insert(const TYPE& dataIn)
{
bool success = false;
if(currSize < capacity)
{
heapData[currSize] = dataIn;
_siftUp(currSize);
currSize++;
success = true;
}
return success;
}
//**************************************************************************
template<typename TYPE>
void Heap<TYPE>::_siftUp(int child)
{
TYPE temp;
int parent;
if(child > 0)
{
parent = _parentOf(child);
if(heapData[child] > heapData[parent])
{
temp = heapData[parent];
heapData[parent] = heapData[child];
heapData[child] = temp;
_siftUp(child);
}
}
}
//**************************************************************************
template<typename TYPE>
bool Heap<TYPE>::remove(TYPE& dataOut)
{
bool success = false;
if(currSize > 0)
{
dataOut = heapData[0];
currSize--;
heapData[0] = heapData[currSize];
_siftDown(0);
success = true;
}
return success;
}
//**************************************************************************
template<typename TYPE>
void Heap<TYPE>::_siftDown(int parent)
{
TYPE temp;
int child = _leftChildOf(parent);
if(child < currSize)
{
if((child + 1 < currSize) && (heapData[child] < heapData[child + 1]))
child++;
if(child)
{
temp = heapData[child];
heapData[child] = heapData[child + 1];
heapData[child + 1] = temp;
_siftDown(child);
}
}
}
//**************************************************************************
template<typename TYPE>
int Heap<TYPE>::_leftChildOf(int p) const
{
return(2 * p + 1);
}
//**************************************************************************
template<typename TYPE>
int Heap<TYPE>::_parentOf(int c) const
{
return((c - 1) / 2);
}
//**************************************************************************
template<typename TYPE>
int Heap<TYPE>::getCapacity() const
{
return capacity;
}
//**************************************************************************
template<typename TYPE>
int Heap<TYPE>::getCurrSize() const
{
return currSize;
}
//**************************************************************************
template<typename TYPE>
bool Heap<TYPE>::viewMax(TYPE& max) const
{
return false
}
#endif
Last edited by Howdy_McGee; April 19th, 2013 at 02:48 PM.
-
April 19th, 2013, 02:40 PM
#2
Re: Implementing a Heap
Please modify your post to put the missing final ] after the [/code at the end so that the code tags work. Also it would be useful to format your code before posting for indents etc.
What debugging of the code have your done to try to identify the problem?
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
April 19th, 2013, 02:50 PM
#3
Re: Implementing a Heap
I've debugged it in VS but it breaks when I assign
Code:
heapData[currSize] = dataIn;
in my insert. I haven't got to my remove yet but I imagine i'll run into the same problems. I set currSize to 0 in my constructor and I run into this problem when I try to insert the first or 1 item.
The error messages tells me that I have an access violation.
-
April 19th, 2013, 02:54 PM
#4
Re: Implementing a Heap
heapData is a pointer, but I don't see where you point it to valid memory.
-
April 19th, 2013, 03:05 PM
#5
Re: Implementing a Heap
In the destructor ~Heap you have
Code:
Heap<TYPE>::~Heap()
{
delete heapData;
currSize = 0;
capacity = 0;
}
which deletes the heapData memory.
However in the constructor Heap you have
Code:
Heap<TYPE>::Heap(int c = 100)
{
capacity = 100;
currSize = 0;
}
You don't use c and you don't allocate memory for heapData using new.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
April 19th, 2013, 03:08 PM
#6
Re: Implementing a Heap
Oh right, I need to initialize my array with capacity, whoops >.>
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|