vtkvmtkMinHeap Class Reference

Implementation of the min heap data structure. More...

#include <vtkvmtkMinHeap.h>

Inheritance diagram for vtkvmtkMinHeap:

Collaboration diagram for vtkvmtkMinHeap:

Public Types
typedef vtkObject	Superclass

Public Member Functions
virtual int	IsA (const char *type)
vtkvmtkMinHeap *	NewInstance () const
void	PrintSelf (ostream &os, vtkIndent indent) VTK_OVERRIDE
void	Initialize ()
int	GetSize ()
void	InsertNextId (vtkIdType id)
void	UpdateId (vtkIdType id)
vtkIdType	GetMin ()
vtkIdType	RemoveMin ()
virtual void	SetMinHeapScalars (vtkDoubleArray *)
virtual vtkDoubleArray *	GetMinHeapScalars ()

Static Public Member Functions
static int	IsTypeOf (const char *type)
static vtkvmtkMinHeap *	SafeDownCast (vtkObjectBase *o)
static vtkvmtkMinHeap *	New ()

Protected Member Functions
virtual vtkObjectBase *	NewInstanceInternal () const
	vtkvmtkMinHeap ()
	~vtkvmtkMinHeap ()
void	Swap (vtkIdType loc0, vtkIdType loc1)
int	IsLeaf (vtkIdType loc)
vtkIdType	GetLeftChild (vtkIdType loc)
vtkIdType	GetRightChild (vtkIdType loc)
vtkIdType	GetParent (vtkIdType loc)
void	SiftUp (vtkIdType loc)
void	SiftDown (vtkIdType loc)
vtkIdType	RemoveAt (vtkIdType loc)

Protected Attributes
vtkIdList *	Heap
vtkIdList *	BackPointers
vtkDoubleArray *	MinHeapScalars

Detailed Description

Implementation of the min heap data structure.

Date

2006/04/06 16:46:43

Revision

1.3

This class is an implementation of the min heap data structure, used to handle a set of values in such a way that the retrieval of the minimum element takes constant time. A min heap is a complete binary tree where the value at each node is equal or less than the value at its children, and it is represented as an array where the children of a node stored at location k are at location 2k and 2k+1 (so that the parent of k is located at k/2). Keeping the min heap ordered after a value is updated or an id is inserted in teh heap takes O(log N).

In the present implementation, values are provided in a vtkDoubleArray, and element ids are inserted in the heap. Backpointers are used to access the heap by id. This class is optimized for working in conjunction with vtkNonManifoldFastMarching.

For more insight see J.A. Sethian, Level Set Methods and Fast Marching Methods, Cambridge University Press, 2nd Edition, 1999.

Warning

Be sure to call Initialize() after defining MinHeapScalars.

See also

vtkNonManifoldFastMarching

Definition at line 44 of file vtkvmtkMinHeap.h.

Member Typedef Documentation

Superclass

typedef vtkObject vtkvmtkMinHeap::Superclass

Definition at line 47 of file vtkvmtkMinHeap.h.

Constructor & Destructor Documentation

vtkvmtkMinHeap()

vtkvmtkMinHeap::vtkvmtkMinHeap ( )

protected

~vtkvmtkMinHeap()

vtkvmtkMinHeap::~vtkvmtkMinHeap ( )

protected

Member Function Documentation

IsTypeOf()

static int vtkvmtkMinHeap::IsTypeOf ( const char *  type )

static

IsA()

virtual int vtkvmtkMinHeap::IsA ( const char *  type )

virtual

SafeDownCast()

static vtkvmtkMinHeap* vtkvmtkMinHeap::SafeDownCast ( vtkObjectBase *  o )

static

NewInstanceInternal()

virtual vtkObjectBase* vtkvmtkMinHeap::NewInstanceInternal ( ) const

protectedvirtual

NewInstance()

vtkvmtkMinHeap* vtkvmtkMinHeap::NewInstance

(

)

const

PrintSelf()

void vtkvmtkMinHeap::PrintSelf	(	ostream &	os,
		vtkIndent	indent
	)

New()

static vtkvmtkMinHeap* vtkvmtkMinHeap::New ( )

static

Initialize()

void vtkvmtkMinHeap::Initialize

(

)

Initializes the heap to an empty state and prepares back pointers. Calls this method before using the min heap once MinHeapScalars have been defined.

SetMinHeapScalars()

virtual void vtkvmtkMinHeap::SetMinHeapScalars ( vtkDoubleArray *  )

virtual

Set/Get the array containing the values indexed by the min heap.

GetMinHeapScalars()

virtual vtkDoubleArray* vtkvmtkMinHeap::GetMinHeapScalars ( )

virtual

Set/Get the array containing the values indexed by the min heap.

GetSize()

int vtkvmtkMinHeap::GetSize

(

)

Get heap size.

InsertNextId()

void vtkvmtkMinHeap::InsertNextId

(

vtkIdType

id

)

Insert an index to a value in HeapScalars in the min heap.

UpdateId()

void vtkvmtkMinHeap::UpdateId

(

vtkIdType

id

)

Tells the min heap that the value indexed by id has changed in MinHeapScalars array.

GetMin()

vtkIdType vtkvmtkMinHeap::GetMin

(

)

Gets the id of the minimum value in the min heap.

RemoveMin()

vtkIdType vtkvmtkMinHeap::RemoveMin

(

)

Gets the id of the minimum value in the min heap and removes it from the min heap.

Swap()

void vtkvmtkMinHeap::Swap ( vtkIdType  loc0, vtkIdType  loc1  )

protected

IsLeaf()

int vtkvmtkMinHeap::IsLeaf ( vtkIdType  loc )

protected

GetLeftChild()

vtkIdType vtkvmtkMinHeap::GetLeftChild ( vtkIdType  loc )

protected

GetRightChild()

vtkIdType vtkvmtkMinHeap::GetRightChild ( vtkIdType  loc )

protected

GetParent()

vtkIdType vtkvmtkMinHeap::GetParent ( vtkIdType  loc )

protected

SiftUp()

void vtkvmtkMinHeap::SiftUp ( vtkIdType  loc )

protected

SiftDown()

void vtkvmtkMinHeap::SiftDown ( vtkIdType  loc )

protected

RemoveAt()

vtkIdType vtkvmtkMinHeap::RemoveAt ( vtkIdType  loc )

protected

Member Data Documentation

Heap

vtkIdList* vtkvmtkMinHeap::Heap

protected

Definition at line 93 of file vtkvmtkMinHeap.h.

BackPointers

vtkIdList* vtkvmtkMinHeap::BackPointers

protected

Definition at line 94 of file vtkvmtkMinHeap.h.

MinHeapScalars

vtkDoubleArray* vtkvmtkMinHeap::MinHeapScalars

protected

Definition at line 96 of file vtkvmtkMinHeap.h.

---

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

• vtkvmtkMinHeap.h