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)
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 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.

: HeapV() { }

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

THeap< TVal, TCmp >::THeap ( const int &  MxVals )

inline

Definition at line 279 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 280 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 281 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 282 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 283 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 301 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 335 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 295 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 293 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 349 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 303 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 297 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 299 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 284 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 313 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 325 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 307 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 287 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 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:

• snap-core/gbase.h