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.