Implementing a Heap
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6

Thread: Implementing a Heap

  1. #1
    Join Date
    Sep 2010
    Posts
    18

    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.

  2. #2
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,556

    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  3. #3
    Join Date
    Sep 2010
    Posts
    18

    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.

  4. #4
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,127

    Re: Implementing a Heap

    heapData is a pointer, but I don't see where you point it to valid memory.

  5. #5
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,556

    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  6. #6
    Join Date
    Sep 2010
    Posts
    18

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center