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

Threaded View

  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.

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