Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
CppHeap.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <algorithm>
9#include <exception>
10#include <vector>
11
12namespace alib {
13
15template < typename T, typename Comparator = std::less < T > >
16class CppHeap {
17public:
18 CppHeap( Comparator comparator = Comparator ( ) ) : m_comparator( comparator ) {
19 }
20
21 // inserts a node with new value into the heap
22 void insert ( const T & value );
23
25 const T & getMax ( ) const {
26 return m_data.front ( );
27 }
28
30 T extractMax ( );
31
33 void mergeWith ( CppHeap < T, Comparator > && that );
34
35 size_t size ( ) const {
36 return m_data.size ( );
37 }
38
39protected:
40 Comparator m_comparator;
41 std::vector < T > m_data;
42};
43
44
45template < typename T, typename Comparator >
46void CppHeap < T, Comparator >::insert ( const T & value ) {
47 m_data.push_back ( value );
48 std::push_heap ( m_data.begin ( ), m_data.end ( ), m_comparator );
49}
50
51template < typename T, typename Comparator >
53 if ( m_data.size ( ) == 0 )
54 throw std::out_of_range ( "Heap is empty." );
55
56 std::pop_heap ( m_data.begin ( ), m_data.end ( ), m_comparator );
57 T res = std::move ( m_data.back ( ) );
58 m_data.pop_back ( );
59 return res;
60}
61
62template < typename T, typename Comparator >
64 m_data.insert ( m_data.end ( ), that.m_data.begin ( ), that.m_data.end ( ) );
65 std::make_heap ( m_data.begin ( ), m_data.end ( ), m_comparator );
66}
67
68} /* namespace alib */
69
heap build using C++ algorithm features
Definition: CppHeap.h:16
Comparator m_comparator
Definition: CppHeap.h:40
void mergeWith(CppHeap< T, Comparator > &&that)
merges this heap with another heap (!! this is a DESTRUCTIVE merge, heap in argument will be cleared ...
Definition: CppHeap.h:63
const T & getMax() const
finds the maximum value in the heap
Definition: CppHeap.h:25
CppHeap(Comparator comparator=Comparator())
Definition: CppHeap.h:18
void insert(const T &value)
Definition: CppHeap.h:46
size_t size() const
Definition: CppHeap.h:35
T extractMax()
finds and removes the maximum value from the heap
Definition: CppHeap.h:52
std::vector< T > m_data
Definition: CppHeap.h:41
Definition: ExceptionHandler.cpp:13
return res
Definition: MinimizeByPartitioning.h:145