SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
THeap< TVal, TCmp > Class Template Reference

Simple heap data structure. More...

#include <gbase.h>

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)
 
THeapoperator= (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 269 of file gbase.h.

Constructor & Destructor Documentation

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

Definition at line 278 of file gbase.h.

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

Definition at line 279 of file gbase.h.

279 : Cmp(), HeapV(MxVals, 0) { }
TVec< TVal > HeapV
Definition: gbase.h:272
TCmp Cmp
Definition: gbase.h:271
template<class TVal, class TCmp = TLss<TVal>>
THeap< TVal, TCmp >::THeap ( const TCmp _Cmp)
inline

Definition at line 280 of file gbase.h.

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

Definition at line 281 of file gbase.h.

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

Definition at line 282 of file gbase.h.

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

Definition at line 283 of file gbase.h.

283 : Cmp(Heap.Cmp), HeapV(Heap.HeapV) { }
TVec< TVal > HeapV
Definition: gbase.h:272
TCmp Cmp
Definition: gbase.h:271

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

301 { HeapV.Add(Val); }
TVec< TVal > HeapV
Definition: gbase.h:272
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 335 of file gbase.h.

335  {
336  const int Top = HoleIdx;
337  int Right = 2*HoleIdx+2;
338  while (Right < Len) {
339  if (Cmp(HeapV[First+Right], HeapV[First+Right-1])) { Right--; }
340  HeapV[First+HoleIdx] = HeapV[First+Right];
341  HoleIdx = Right; Right = 2*(Right+1); }
342  if (Right == Len) {
343  HeapV[First+HoleIdx] = HeapV[First+Right-1];
344  HoleIdx = Right-1; }
345  PushHeap(First, HoleIdx, Top, Val);
346 }
TVec< TVal > HeapV
Definition: gbase.h:272
TCmp Cmp
Definition: gbase.h:271
void PushHeap(const int &First, int HoleIdx, const int &Top, TVal Val)
Definition: gbase.h:325
int Len() const
Returns the number of elements in the heap.
Definition: gbase.h:293
template<class TVal, class TCmp = TLss<TVal>>
bool THeap< TVal, TCmp >::Empty ( ) const
inline

Tests whether the heap is empty.

Definition at line 295 of file gbase.h.

295 { return HeapV.Empty(); }
TVec< TVal > HeapV
Definition: gbase.h:272
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 293 of file gbase.h.

293 { return HeapV.Len(); }
TVec< TVal > HeapV
Definition: gbase.h:272
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
template<class TVal , class TCmp >
void THeap< TVal, TCmp >::MakeHeap ( const int &  First,
const int &  Len 
)
private

Definition at line 349 of file gbase.h.

349  {
350  if (Len < 2) { return; }
351  int Parent = (Len-2)/2;
352  while (true) {
353  AdjustHeap(First, Parent, Len, HeapV[First+Parent]);
354  if (Parent == 0) { return; }
355  Parent--;
356  }
357 }
TVec< TVal > HeapV
Definition: gbase.h:272
void AdjustHeap(const int &First, int HoleIdx, const int &Len, TVal Val)
Definition: gbase.h:335
int Len() const
Returns the number of elements in the heap.
Definition: gbase.h:293
template<class TVal, class TCmp = TLss<TVal>>
void THeap< TVal, TCmp >::MakeHeap ( )
inline

Builds a heap from a set of elements.

Definition at line 303 of file gbase.h.

303 { MakeHeap(0, Len()); }
void MakeHeap()
Builds a heap from a set of elements.
Definition: gbase.h:303
int Len() const
Returns the number of elements in the heap.
Definition: gbase.h:293
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 297 of file gbase.h.

297 { return HeapV; }
TVec< TVal > HeapV
Definition: gbase.h:272
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 299 of file gbase.h.

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

Definition at line 284 of file gbase.h.

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

Removes the top element from the heap.

Definition at line 313 of file gbase.h.

313  {
314  IAssert(! HeapV.Empty());
315  const TVal Top = HeapV[0];
316  HeapV[0] = HeapV.Last();
317  HeapV.DelLast();
318  if (! HeapV.Empty()) {
319  AdjustHeap(0, 0, HeapV.Len(), HeapV[0]);
320  }
321  return Top;
322 }
#define IAssert(Cond)
Definition: bd.h:262
TVec< TVal > HeapV
Definition: gbase.h:272
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
void AdjustHeap(const int &First, int HoleIdx, const int &Len, TVal Val)
Definition: gbase.h:335
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 325 of file gbase.h.

325  {
326  int Parent = (HoleIdx-1)/2;
327  while (HoleIdx > Top && Cmp(HeapV[First+Parent], Val)) {
328  HeapV[First+HoleIdx] = HeapV[First+Parent];
329  HoleIdx = Parent; Parent = (HoleIdx-1)/2;
330  }
331  HeapV[First+HoleIdx] = Val;
332 }
TVec< TVal > HeapV
Definition: gbase.h:272
TCmp Cmp
Definition: gbase.h:271
template<class TVal, class TCmp >
void THeap< TVal, TCmp >::PushHeap ( const TVal &  Val)

Pushes an element Val to the heap.

Definition at line 307 of file gbase.h.

307  {
308  HeapV.Add(Val);
309  PushHeap(0, HeapV.Len()-1, 0, Val);
310 }
TVec< TVal > HeapV
Definition: gbase.h:272
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void PushHeap(const int &First, int HoleIdx, const int &Top, TVal Val)
Definition: gbase.h:325
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 287 of file gbase.h.

287 { return HeapV[0]; }
TVec< TVal > HeapV
Definition: gbase.h:272

Member Data Documentation

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

Definition at line 271 of file gbase.h.

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

Definition at line 272 of file gbase.h.


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