SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Public Member Functions | Private Member Functions | Private Attributes | List of all members
THeap< TVal, TCmp > Class Template Reference

Simple heap data structure. More...

#include <gbase.h>

Collaboration diagram for THeap< TVal, TCmp >:
Collaboration graph
[legend]

Public Member Functions

 THeap ()
 
 THeap (const int &MxVals)
 
 THeap (const TCmp &_Cmp)
 
 THeap (const TVec< TVal > &Vec)
 
 THeap (const TVec< TVal > &Vec, const TCmp &_Cmp)
 
 THeap (const THeap &Heap)
 
THeap & operator= (const THeap &H)
 
const TVal & TopHeap () const
 Returns a reference to the element at the top of the heap (the largest element of the heap). More...
 
void PushHeap (const TVal &Val)
 Pushes an element Val to the heap. More...
 
TVal PopHeap ()
 Removes the top element from the heap. More...
 
int Len () const
 Returns the number of elements in the heap. More...
 
bool Empty () const
 Tests whether the heap is empty. More...
 
const TVec< TVal > & operator() () const
 Returns a reference to the vector containing the elements of the heap. More...
 
TVec< TVal > & operator() ()
 Returns a reference to the vector containing the elements of the heap. More...
 
void Add (const TVal &Val)
 Adds an element to the data structure. Heap property is not maintained by Add() and thus after all the elements are added MakeHeap() needs to be called. More...
 
void MakeHeap ()
 Builds a heap from a set of elements. More...
 

Private Member Functions

void PushHeap (const int &First, int HoleIdx, const int &Top, TVal Val)
 
void AdjustHeap (const int &First, int HoleIdx, const int &Len, TVal Val)
 
void MakeHeap (const int &First, const int &Len)
 

Private Attributes

TCmp Cmp
 
TVec< TVal > HeapV
 

Detailed Description

template<class TVal, class TCmp = TLss<TVal>>
class THeap< TVal, TCmp >

Simple heap data structure.

Data structure provides insertion of elements, and inspection and removal of the top element. It is guaranteed that the top element is the largest element in the heap, where the function object TCmp is used for comparisons.

Definition at line 256 of file gbase.h.

Constructor & Destructor Documentation

template<class TVal, class TCmp = TLss<TVal>>
THeap< TVal, TCmp >::THeap ( )
inline

Definition at line 265 of file gbase.h.

265 : HeapV() { }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
template<class TVal, class TCmp = TLss<TVal>>
THeap< TVal, TCmp >::THeap ( const int &  MxVals)
inline

Definition at line 266 of file gbase.h.

266 : Cmp(), HeapV(MxVals, 0) { }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
THeap::Cmp
TCmp Cmp
Definition: gbase.h:258
template<class TVal, class TCmp = TLss<TVal>>
THeap< TVal, TCmp >::THeap ( const TCmp &  _Cmp)
inline

Definition at line 267 of file gbase.h.

267 : Cmp(_Cmp), HeapV() { }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
THeap::Cmp
TCmp Cmp
Definition: gbase.h:258
template<class TVal, class TCmp = TLss<TVal>>
THeap< TVal, TCmp >::THeap ( const TVec< TVal > &  Vec)
inline

Definition at line 268 of file gbase.h.

268 : Cmp(), HeapV(Vec) { MakeHeap(); }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
THeap::MakeHeap
void MakeHeap()
Builds a heap from a set of elements.
Definition: gbase.h:290
THeap::Cmp
TCmp Cmp
Definition: gbase.h:258
template<class TVal, class TCmp = TLss<TVal>>
THeap< TVal, TCmp >::THeap ( const TVec< TVal > &  Vec,
const TCmp &  _Cmp 
)
inline

Definition at line 269 of file gbase.h.

269 : Cmp(_Cmp), HeapV(Vec) { MakeHeap(); }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
THeap::MakeHeap
void MakeHeap()
Builds a heap from a set of elements.
Definition: gbase.h:290
THeap::Cmp
TCmp Cmp
Definition: gbase.h:258
template<class TVal, class TCmp = TLss<TVal>>
THeap< TVal, TCmp >::THeap ( const THeap< TVal, TCmp > &  Heap)
inline

Definition at line 270 of file gbase.h.

270 : Cmp(Heap.Cmp), HeapV(Heap.HeapV) { }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
THeap::Cmp
TCmp Cmp
Definition: gbase.h:258

Member Function Documentation

template<class TVal, class TCmp = TLss<TVal>>
void THeap< TVal, TCmp >::Add ( const TVal &  Val)
inline

Adds an element to the data structure. Heap property is not maintained by Add() and thus after all the elements are added MakeHeap() needs to be called.

Definition at line 288 of file gbase.h.

288 { HeapV.Add(Val); }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
template<class TVal, class TCmp >
void THeap< TVal, TCmp >::AdjustHeap ( const int &  First,
int  HoleIdx,
const int &  Len,
TVal  Val 
)
private

Definition at line 322 of file gbase.h.

References Cmp().

322  {
323  const int Top = HoleIdx;
324  int Right = 2*HoleIdx+2;
325  while (Right < Len) {
326  if (Cmp(HeapV[First+Right], HeapV[First+Right-1])) { Right--; }
327  HeapV[First+HoleIdx] = HeapV[First+Right];
328  HoleIdx = Right; Right = 2*(Right+1); }
329  if (Right == Len) {
330  HeapV[First+HoleIdx] = HeapV[First+Right-1];
331  HoleIdx = Right-1; }
332  PushHeap(First, HoleIdx, Top, Val);
333 }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
THeap::Cmp
TCmp Cmp
Definition: gbase.h:258
THeap::PushHeap
void PushHeap(const int &First, int HoleIdx, const int &Top, TVal Val)
Definition: gbase.h:312
THeap::Len
int Len() const
Returns the number of elements in the heap.
Definition: gbase.h:280

Here is the call graph for this function:

template<class TVal, class TCmp = TLss<TVal>>
bool THeap< TVal, TCmp >::Empty ( ) const
inline

Tests whether the heap is empty.

Definition at line 282 of file gbase.h.

282 { return HeapV.Empty(); }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
template<class TVal, class TCmp = TLss<TVal>>
int THeap< TVal, TCmp >::Len ( ) const
inline

Returns the number of elements in the heap.

Definition at line 280 of file gbase.h.

Referenced by THeap< TTriple >::MakeHeap().

280 { return HeapV.Len(); }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575

Here is the caller graph for this function:

template<class TVal , class TCmp >
void THeap< TVal, TCmp >::MakeHeap ( const int &  First,
const int &  Len 
)
private

Definition at line 336 of file gbase.h.

336  {
337  if (Len < 2) { return; }
338  int Parent = (Len-2)/2;
339  while (true) {
340  AdjustHeap(First, Parent, Len, HeapV[First+Parent]);
341  if (Parent == 0) { return; }
342  Parent--;
343  }
344 }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
THeap::AdjustHeap
void AdjustHeap(const int &First, int HoleIdx, const int &Len, TVal Val)
Definition: gbase.h:322
THeap::Len
int Len() const
Returns the number of elements in the heap.
Definition: gbase.h:280
template<class TVal, class TCmp = TLss<TVal>>
void THeap< TVal, TCmp >::MakeHeap ( )
inline

Builds a heap from a set of elements.

Definition at line 290 of file gbase.h.

Referenced by THeap< TTriple >::MakeHeap(), and THeap< TTriple >::THeap().

290 { MakeHeap(0, Len()); }
THeap::MakeHeap
void MakeHeap()
Builds a heap from a set of elements.
Definition: gbase.h:290
THeap::Len
int Len() const
Returns the number of elements in the heap.
Definition: gbase.h:280

Here is the caller graph for this function:

template<class TVal, class TCmp = TLss<TVal>>
const TVec<TVal>& THeap< TVal, TCmp >::operator() ( ) const
inline

Returns a reference to the vector containing the elements of the heap.

Definition at line 284 of file gbase.h.

284 { return HeapV; }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
template<class TVal, class TCmp = TLss<TVal>>
TVec<TVal>& THeap< TVal, TCmp >::operator() ( )
inline

Returns a reference to the vector containing the elements of the heap.

Definition at line 286 of file gbase.h.

286 { return HeapV; }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
template<class TVal, class TCmp = TLss<TVal>>
THeap& THeap< TVal, TCmp >::operator= ( const THeap< TVal, TCmp > &  H)
inline

Definition at line 271 of file gbase.h.

271 { Cmp=H.Cmp; HeapV=H.HeapV; return *this; }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
THeap::Cmp
TCmp Cmp
Definition: gbase.h:258
template<class TVal , class TCmp >
TVal THeap< TVal, TCmp >::PopHeap ( )

Removes the top element from the heap.

Definition at line 300 of file gbase.h.

References IAssert.

300  {
301  IAssert(! HeapV.Empty());
302  const TVal Top = HeapV[0];
303  HeapV[0] = HeapV.Last();
304  HeapV.DelLast();
305  if (! HeapV.Empty()) {
306  AdjustHeap(0, 0, HeapV.Len(), HeapV[0]);
307  }
308  return Top;
309 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
THeap::AdjustHeap
void AdjustHeap(const int &First, int HoleIdx, const int &Len, TVal Val)
Definition: gbase.h:322
TVec::DelLast
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
template<class TVal, class TCmp >
void THeap< TVal, TCmp >::PushHeap ( const int &  First,
int  HoleIdx,
const int &  Top,
TVal  Val 
)
private

Definition at line 312 of file gbase.h.

References Cmp().

312  {
313  int Parent = (HoleIdx-1)/2;
314  while (HoleIdx > Top && Cmp(HeapV[First+Parent], Val)) {
315  HeapV[First+HoleIdx] = HeapV[First+Parent];
316  HoleIdx = Parent; Parent = (HoleIdx-1)/2;
317  }
318  HeapV[First+HoleIdx] = Val;
319 }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
THeap::Cmp
TCmp Cmp
Definition: gbase.h:258

Here is the call graph for this function:

template<class TVal, class TCmp >
void THeap< TVal, TCmp >::PushHeap ( const TVal &  Val)

Pushes an element Val to the heap.

Definition at line 294 of file gbase.h.

294  {
295  HeapV.Add(Val);
296  PushHeap(0, HeapV.Len()-1, 0, Val);
297 }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THeap::PushHeap
void PushHeap(const int &First, int HoleIdx, const int &Top, TVal Val)
Definition: gbase.h:312
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
template<class TVal, class TCmp = TLss<TVal>>
const TVal& THeap< TVal, TCmp >::TopHeap ( ) const
inline

Returns a reference to the element at the top of the heap (the largest element of the heap).

Definition at line 274 of file gbase.h.

274 { return HeapV[0]; }
THeap::HeapV
TVec< TVal > HeapV
Definition: gbase.h:259

Member Data Documentation

template<class TVal, class TCmp = TLss<TVal>>
TCmp THeap< TVal, TCmp >::Cmp
private

Definition at line 258 of file gbase.h.

Referenced by THeap< TTriple >::operator=().

template<class TVal, class TCmp = TLss<TVal>>
TVec<TVal> THeap< TVal, TCmp >::HeapV
private

Definition at line 259 of file gbase.h.

Referenced by THeap< TTriple >::Add(), THeap< TTriple >::Empty(), THeap< TTriple >::Len(), THeap< TTriple >::operator()(), THeap< TTriple >::operator=(), and THeap< TTriple >::TopHeap().

The documentation for this class was generated from the following file: