CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6
  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
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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)

  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
    Location
    Florida
    Posts
    12,635

    Re: Implementing a Heap

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

  5. #5
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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)

  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
  •  





Click Here to Expand Forum to Full Width

Featured