SNAP Library 2.0, Developer Reference  2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Member Functions | Private Member Functions | Private Attributes
THeap< TVal, TCmp > Class Template Reference

Simple heap data structure. More...

#include <gbase.h>

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

List of all members.

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).
void PushHeap (const TVal &Val)
 Pushes an element Val to the heap.
TVal PopHeap ()
 Removes the top element from the heap.
int Len () const
 Returns the number of elements in the heap.
bool Empty () const
 Tests whether the heap is empty.
const TVec< TVal > & operator() () const
 Returns a reference to the vector containing the elements of the heap.
TVec< TVal > & operator() ()
 Returns a reference to the vector containing the elements of the heap.
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.
void MakeHeap ()
 Builds a heap from a set of elements.

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 228 of file gbase.h.

Constructor & Destructor Documentation

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

Definition at line 237 of file gbase.h.

: HeapV() { }
template<class TVal, class TCmp = TLss<TVal>>
THeap< TVal, TCmp >::THeap ( const int &  MxVals) [inline]

Definition at line 238 of file gbase.h.

: Cmp(), HeapV(0, MxVals) { }
template<class TVal, class TCmp = TLss<TVal>>
THeap< TVal, TCmp >::THeap ( const TCmp &  _Cmp) [inline]

Definition at line 239 of file gbase.h.

: Cmp(_Cmp), HeapV() { }
template<class TVal, class TCmp = TLss<TVal>>
THeap< TVal, TCmp >::THeap ( const TVec< TVal > &  Vec) [inline]

Definition at line 240 of file gbase.h.

: Cmp(), HeapV(Vec) { MakeHeap(); }
template<class TVal, class TCmp = TLss<TVal>>
THeap< TVal, TCmp >::THeap ( const TVec< TVal > &  Vec,
const TCmp &  _Cmp 
) [inline]

Definition at line 241 of file gbase.h.

: Cmp(_Cmp), HeapV(Vec) { MakeHeap(); }
template<class TVal, class TCmp = TLss<TVal>>
THeap< TVal, TCmp >::THeap ( const THeap< TVal, TCmp > &  Heap) [inline]

Definition at line 242 of file gbase.h.

: Cmp(Heap.Cmp), HeapV(Heap.HeapV) { }

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 260 of file gbase.h.

Referenced by TSnap::TSnapDetail::TCNMQMatrix::Init().

{ HeapV.Add(Val); }

Here is the caller graph for this function:

template<class TVal, class TCmp >
void THeap< TVal, TCmp >::AdjustHeap ( const int &  First,
int  HoleIdx,
const int &  Len,
TVal  Val 
) [private]

Definition at line 294 of file gbase.h.

References Cmp().

                                                                                          {
  const int Top = HoleIdx;
  int Right = 2*HoleIdx+2;
  while (Right < Len) {
    if (Cmp(HeapV[First+Right], HeapV[First+Right-1])) { Right--; }
    HeapV[First+HoleIdx] = HeapV[First+Right];
    HoleIdx = Right;  Right = 2*(Right+1); }
  if (Right == Len) {
    HeapV[First+HoleIdx] = HeapV[First+Right-1];
    HoleIdx = Right-1; }
  PushHeap(First, HoleIdx, Top, Val);
}

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 254 of file gbase.h.

Referenced by TSnap::TSnapDetail::TCNMQMatrix::FindMxQEdge().

{ return HeapV.Empty(); }

Here is the caller graph for this function:

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 252 of file gbase.h.

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

{ return HeapV.Len(); }

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 308 of file gbase.h.

Referenced by TSnap::TSnapDetail::TCNMQMatrix::Init().

                                                                 {
  if (Len < 2) { return; }
  int Parent = (Len-2)/2;
  while (true) {
    AdjustHeap(First, Parent, Len, HeapV[First+Parent]);
    if (Parent == 0) { return; }
    Parent--;
  }
}

Here is the caller graph for this function:

template<class TVal, class TCmp = TLss<TVal>>
void THeap< TVal, TCmp >::MakeHeap ( ) [inline]

Builds a heap from a set of elements.

Definition at line 262 of file gbase.h.

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

{ MakeHeap(0, Len()); }

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 256 of file gbase.h.

{ return HeapV; }
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 258 of file gbase.h.

{ return HeapV; }
template<class TVal, class TCmp = TLss<TVal>>
THeap& THeap< TVal, TCmp >::operator= ( const THeap< TVal, TCmp > &  H) [inline]

Definition at line 243 of file gbase.h.

{ Cmp=H.Cmp; HeapV=H.HeapV; return *this; }
template<class TVal , class TCmp >
TVal THeap< TVal, TCmp >::PopHeap ( )

Removes the top element from the heap.

Definition at line 272 of file gbase.h.

References IAssert.

Referenced by TSnap::TSnapDetail::TCNMQMatrix::FindMxQEdge().

                                {
  IAssert(! HeapV.Empty());
  const TVal Top = HeapV[0];
  HeapV[0] = HeapV.Last();
  HeapV.DelLast();
  if (! HeapV.Empty()) {
    AdjustHeap(0, 0, HeapV.Len(), HeapV[0]);
  }
  return Top;
}

Here is the caller graph for this function:

template<class TVal, class TCmp >
void THeap< TVal, TCmp >::PushHeap ( const int &  First,
int  HoleIdx,
const int &  Top,
TVal  Val 
) [private]

Definition at line 284 of file gbase.h.

References Cmp().

Referenced by TSnap::TSnapDetail::TCNMQMatrix::MergeBestQ().

                                                                                        {
  int Parent = (HoleIdx-1)/2;
  while (HoleIdx > Top && Cmp(HeapV[First+Parent], Val)) {
    HeapV[First+HoleIdx] = HeapV[First+Parent];
    HoleIdx = Parent;  Parent = (HoleIdx-1)/2;
  }
  HeapV[First+HoleIdx] = Val;
}

Here is the call graph for this function:

Here is the caller 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 266 of file gbase.h.

                                                {
  HeapV.Add(Val);
  PushHeap(0, HeapV.Len()-1, 0, Val);
}
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 246 of file gbase.h.

{ return HeapV[0]; }

Member Data Documentation

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

Definition at line 230 of file gbase.h.

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

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

Definition at line 231 of file gbase.h.

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

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