C++ Heap Template

For some reason heap container is missing in C++  standard template library. Instead they have provided push_heap, pop_heap and make_heap opeartion as seperate functions, which is obviating gory details of a simple container and so unnecessary. I've always wished that there be a simple container like rb_tree, which can manage the property. So here it is-

C++ Source


Click here to download the code


Description

This is very simple container following heap property. It provides two basic classes MinHeap and MaxHeap. This template can be inherited to create more complex templates like treap.

  • Push(T& element): push the object onto heap. (worst case complexity ln n)
  • T& pop(): pop the min/max element out of heap and rearrange the heap (worst case complexity ln n)
  • All other methods provided by STL-vector, including iterators.
  • Complex objects require comparision (< and >) and assignment operators to be contained in this container.

Example

MinHeap<int> my_heap;
my_heap.push(10); 
int element = my_heap.pop();

Disclaimer

///////////////////////////////////////////////////////////////////
// Copyright (c) 2006 Rohit Sharma. All rights reserved. 
// This program is free software; you can redistribute it and/or 
// modify it under the terms as GNU General Public License. 
///////////////////////////////////////////////////////////////////

Copyright: Rohit Sharma,. 2006. Last update June 21, 2006 counter