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;
while (!intheap.empty())
a =;

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 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.