This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

| Template Heap Class Submitted by

Disclaimer: I cannot be held responsible for any faults in, or errors caused by, the code I am submitting although I hope that the code will not cause problems for it's users. Introduction: One day I was programming a ttf loading program and needed an array of std::priority_queue. I could not run the program since there occurred a runtime error in the std code. Anyway I decided to make my own template heap class, and here it is. Here are some pointers on how to use it:

    #include "Heap.h"
    ...
    jsh::heap<int, jsh::greater intheap;
    int a;
    intheap.push(a);
    while (!intheap.empty())
    {
    a = heap.top();
    heap.pop();
    }
    ...

The 'jsh::greater' is a structure defined in the Heap.h header. It is used for sorting the heap in increasing greatness. The jsh::less struct is used for sorting the heap elements in increasing lessness. Of course you could make your own comparison structure to use. Write to me at jesper@atrad.se if you have questions regarding the code.

Download Associated File: TemplateHeap.h (2,765 bytes)

    /*
    ++	File name: Heap.h
    ++	File comments: Use this code in any way if you so desire but
    		include this copyright notice.
    ++	Copyright (c) 2003, Jesper Öqvist
    */

    //created: 2003-02-25
    //last updated: 2003-02-28

    #ifndef _JSH_HEAP_H
    #define _JSH_HEAP_H

    namespace jsh{

    struct greater
    {
    public:
    	template <class _t>
    	bool operator()(const _t& _a, const _t& _b) const {return (_a > _b);}
    };

    struct less
    {
    public:
    	template <class _t>
    	bool operator()(const _t& _a, const _t& _b) const {return (_a < _b);}
    };

    template <typename _t, typename _c = less>
    class heap
    {
    	struct _node
    	{
    		_t _value;
    		_node* _next;

    		_node() {}
    		_node(const _node& _a): _value(_a._value), _next(_a._next) {}
    		_node& operator=(const _node& _a) {_value = _a._value;_next = _a._next;}
    		~_node() {}
    	};
    	_node* _top;
    	_node* _bottom;

    	heap<_t, _c>(const heap<_t, _c>& _a): _top(NULL), _bottom(NULL) {}
    	heap<_t, _c>& operator=(const heap<_t, _c>& _a) {return *this;}

    public:
    	heap<_t, _c>(): _top(NULL), _bottom(NULL) {}
    	~heap<_t, _c>() {clear();}

    	void push(const _t& _a);//push a new value onto the heap
    	void pop();//remove the top value
    	const _t& top() {return _top->_value;}//what's the top value?
    	bool empty() {return (_top == NULL);}//is the heap empty?
    	void clear() {while (!empty()) pop();}//removes all nodes of the heap
    };

    template <typename _t, typename _c>
    void heap<_t, _c>::push(const _t& _a)
    {
    	if (_top != NULL)
    	{
    		//test last value to avoid comparing all values if possible
    		if (_c()(_a, _bottom->_value)) goto _push_bottom;
    		else
    		{
    			//test first value to avoid unnecessary comparisons
    			if (!_c()(_a, _top->_value))
    			{
    				_node* _new = new _node;
    				_new->_value = _a;
    				_new->_next = _top;
    				_top = _new;
    				return;
    			}
    			else
    			{
    				_node* _current = _top;
    				_node* _last = _current;
    				//compare values untill comparison fails
    				while (_c()(_a, _current->_value))
    				{
    					_last = _current;
    					_current = _last->_next;
    				}
    				_node* _new = new _node;
    				_new->_value = _a;
    				_new->_next = _current;
    				_last->_next = _new;
    				return;
    			}
    		}
    _push_bottom:
    		_node* _new = new _node;
    		_new->_value = _a;
    		_new->_next = _bottom->_next;
    		_bottom->_next = _new;
    		_bottom = _new;
    		return;
    	}
    	else
    	{
    		//if there is no top / the heap is empty:
    		_top = new _node;
    		_top->_value = _a;
    		_top->_next = NULL;
    		_bottom = _top;
    	}
    }

    template <typename _t, typename _c>
    void heap<_t, _c>::pop()
    {
    	if (_top == NULL) return;
    	if (_top == _bottom)
    	{
    		delete _top;
    		_top = _bottom = NULL;
    	}
    	else
    	{
    		_node* _tmp = _top->_next;
    		delete _top;
    		_top = _tmp;
    	}
    }

    };

    #endif _JSH_HEAP_H

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.