SNAP Library 2.1, User Reference  2013-09-25 10:47:25
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>

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

Constructor & Destructor Documentation

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

Definition at line 262 of file gbase.h.

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

Definition at line 263 of file gbase.h.

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

Definition at line 264 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 265 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 266 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 267 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 285 of file gbase.h.

{ HeapV.Add(Val); }
template<class TVal, class TCmp >
void THeap< TVal, TCmp >::AdjustHeap ( const int &  First,
int  HoleIdx,
const int &  Len,
TVal  Val 
) [private]

Definition at line 319 of file gbase.h.

                                                                                          {
  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);
}
template<class TVal, class TCmp = TLss<TVal>>
bool THeap< TVal, TCmp >::Empty ( ) const [inline]

Tests whether the heap is empty.

Definition at line 279 of file gbase.h.

{ return HeapV.Empty(); }
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 277 of file gbase.h.

{ return HeapV.Len(); }
template<class TVal , class TCmp >
void THeap< TVal, TCmp >::MakeHeap ( const int &  First,
const int &  Len 
) [private]

Definition at line 333 of file gbase.h.

                                                                 {
  if (Len < 2) { return; }
  int Parent = (Len-2)/2;
  while (true) {
    AdjustHeap(First, Parent, Len, HeapV[First+Parent]);
    if (Parent == 0) { return; }
    Parent--;
  }
}
template<class TVal, class TCmp = TLss<TVal>>
void THeap< TVal, TCmp >::MakeHeap ( ) [inline]

Builds a heap from a set of elements.

Definition at line 287 of file gbase.h.

{ MakeHeap(0, Len()); }
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 281 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 283 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 268 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 297 of file gbase.h.

                                {
  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;
}
template<class TVal, class TCmp >
void THeap< TVal, TCmp >::PushHeap ( const int &  First,
int  HoleIdx,
const int &  Top,
TVal  Val 
) [private]

Definition at line 309 of file gbase.h.

                                                                                        {
  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;
}
template<class TVal, class TCmp >
void THeap< TVal, TCmp >::PushHeap ( const TVal &  Val)

Pushes an element Val to the heap.

Definition at line 291 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 271 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 255 of file gbase.h.

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

Definition at line 256 of file gbase.h.

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