heap.h File Reference

Definition of a binary heap used to implement priority queues. More...

#include "vector.h"

Data Structures
struct	Theap
	A generic binary heap. More...
Functions
boolean	LessThanID (void a, void b, void *userData)
	Comparison operator for identifiers.
boolean	LessThanDouble (void a, void b, void *userData)
	Comparison operator for doubles.
boolean	LessThanPtr (void a, void b, void *userData)
	Comparison operator for pointers.
void	InitHeap (unsigned int ele_size, void(Copy)(void , void ), void(Delete)(void ), boolean(LessThan)(void , void , void ), void userData, boolean hasIDs, unsigned int max_ele, Theap *heap)
	Constructor.
void	CopyHeap (Theap h_dst, Theap h_src)
	Copy constructor.
unsigned int	HeapSize (Theap *heap)
	Gets the number of elements in a heap.
boolean	HeapEmpty (Theap *heap)
	Checks if a heap is empty.
void	AddElement2Heap (unsigned int id, void e, Theap heap)
	Adds an element to the heap.
void	UpdateHeapElement (unsigned int id, Theap *heap)
	Updates the position of an element in the heap.
void *	GetHeapElement (unsigned int i, Theap *heap)
	Returns a pointer to a heap element.
void *	GetHeapElementWithID (unsigned int id, Theap *heap)
	Returns a pointer to a heap element given the element identifier.
unsigned int	GetHeapPosition (unsigned int id, Theap *heap)
	Returns the current position in the heap of an element given its identifier.
void	ExtractMinElement (void e, Theap heap)
	Extracts and removes the minimal element of a heap.
void	ResetHeap (Theap *heap)
	Resets a heap.
void	DeleteHeap (Theap *heap)
	Destructor.

Detailed Description

Implementation of a generic binary heap to be used to implement priority queues. The implementation works on generic objects as far as they have

A copy constructor.
A destructor.
A comparison operator identifying the lower of two given objects.

The implementation heavely relies in the use of the vector structure and, thus, default opeators (constructor, destructor, comparison) for doubles, integers, and pointers are already provided.

The only distintive feature of this implementation is that element can have an identifier assigned by the caller attending to the semantic of the objects in the heap. This is useful to efficiently retrive the position in the heap of an element given its identifier. This is required in several applications (for instance by efficient incremental A* algorithms).

See also:: Theap, heap.c.

Definition in file heap.h.

Function Documentation

boolean LessThanID	(	void *	a,
		void *	b,
		void *	userData
	)

Comparison operator for identifiers identifying the lower of the two given identifiers.

Parameters:

	a	Pointer to the first identifier to compare.
	b	Pointer to the second identifier to compare.
	userData	Pointer to the user data given when defining the heap. It is not used in this case but given for compatibility with more complex LessThan operators.

Returns:: TRUE if the first input is smaller than the second.

Definition at line 156 of file heap.c.

boolean LessThanDouble	(	void *	a,
		void *	b,
		void *	userData
	)

Comparison operator for doubles identifying the lower of the two given doubles.

Parameters:

	a	Pointer to the first double to compare.
	b	Pointer to the second double to compare.
	userData	Pointer to the user data given when defining the heap. It is not used in this case but given for compatibility with more complex LessThan operators.

Returns:: TRUE if the first input is smaller than the second.

Definition at line 161 of file heap.c.

boolean LessThanPtr	(	void *	a,
		void *	b,
		void *	userData
	)

Comparison operator for pointers identifying the lower of the two given pointers.

Parameters:

	a	Pointer to the first pointer to compare.
	b	Pointer to the second pointer to compare.
	userData	Pointer to the user data given when defining the heap. It is not used in this case but given for compatibility with more complex LessThan operators.

Returns:: TRUE if the first input is smaller than the second.

Definition at line 166 of file heap.c.

void InitHeap	(	unsigned int	ele_size,
		void()(void , void *)	Copy,
		void()(void )	Delete,
		boolean()(void , void , void )	LessThan,
		void *	userData,
		boolean	hasIDs,
		unsigned int	max_ele,
		Theap *	heap
	)

Initializes an empty heap Examples of use:

InitHeap(sizeof(unsigned int),CopyID,DeleteID,LessThanID,NULL,MaxNumEle,&heap);
InitHeap(sizeof(double),CopyDouble,DeleteDouble,LessThanDouble,NULL,MaxNumEle,&heap);
InitHeap(sizeof(void *),CopyPtr,DeletePtr,LessThanPtr,NULL,MaxNumEle,&heap);

Parameters:

	ele_size	Number of bytes taken by each element in the list.
	Copy	Copy constructor for the elements in the list.
	Delete	Destructor for the elements in the list.
	LessThan	The operator to use when sorting the elements in the heap. Smaller elements are in the top of the heap and, thus, are returned first using ExtractMinElement.
	userData	The pointer to the data to pass to the LessThan operator as a third parameter.
	hasIDs	TRUE if elements in the heap have will have an identifier.
	max_ele	Initial number of elements in the heap. This can be extended on-line but the execution it is more efficient if we have a good guess for this value.
	heap	The heap to initialize.

Definition at line 172 of file heap.c.

References CopyID(), Theap::data, Theap::data2id, DeleteID(), Theap::hasIDs, Theap::id2data, InitVector(), Theap::last, Theap::LessThan, and Theap::userData.

Referenced by InitHeapOfBoxes().

Here is the call graph for this function:

Here is the caller graph for this function:

void CopyHeap	(	Theap *	h_dst,
		Theap *	h_src
	)

Copies h_src into h_dst. This is a constructor and, thus, h_dst is initialized inside this function.

Parameters:

	h_dst	The heap to define.
	h_src	The heap from where to get the data.

Definition at line 194 of file heap.c.

References CopyVector(), Theap::data, Theap::data2id, Theap::hasIDs, Theap::id2data, Theap::last, Theap::LessThan, and Theap::userData.

Here is the call graph for this function:

unsigned int HeapSize ( Theap * heap )

Returns the number of elements in a heap.

Parameters:

heap

The heap to query.

Returns:: The number of elements in the heap.

Definition at line 208 of file heap.c.

References Theap::last.

Referenced by Heap2List(), HeapOfBoxesMaxDiagonal(), HeapOfBoxesMaxSize(), HeapOfBoxesVolume(), MPI_SolveCuikSystem(), and PrintHeapOfBoxes().

Here is the caller graph for this function:

boolean HeapEmpty ( Theap * heap )

Checks if a heap is empty

Parameters:

heap

The heap to query.

Returns:: TRUE if there are no elements in the heap.

Definition at line 213 of file heap.c.

References Theap::last.

Referenced by MPI_SolveCuikSystem(), and SolveCuikSystem().

Here is the caller graph for this function:

void AddElement2Heap	(	unsigned int	id,
		void *	e,
		Theap *	heap
	)

Adds an element to the heap.

Parameters:

	id	The identifier of the element.
	e	The element add to the heap.
	heap	The heap to update.

Definition at line 218 of file heap.c.

References Theap::data, Theap::data2id, Theap::hasIDs, HeapUp(), Theap::id2data, Theap::last, and SetVectorElement().

Referenced by AddBox2HeapOfBoxes(), and AddList2Heap().

Here is the call graph for this function:

Here is the caller graph for this function:

void UpdateHeapElement	(	unsigned int	id,
		Theap *	heap
	)

Updates the position of an element in the heap given its identifier.

This is to be used after the priority of an object has been updated.

This function only works for heaps whose elements have an associated identifier (the identifier is required to locate the element to update in the heap). If the elements have no asssocated identifer this function triggers an error.

Parameters:

	id	The identifier the element whose priority need to be reconsidered.
	heap	The heap to update.

Definition at line 232 of file heap.c.

References Error(), GetHeapPosition(), Theap::hasIDs, HeapDown(), and HeapUp().

Here is the call graph for this function:

void* GetHeapElement	(	unsigned int	i,
		Theap *	heap
	)

Returns a pointer to a given heap element.

Parameters:

	i	The heap position to retrive.
	heap	The heap to query.

Returns:: A pointer to the requested heap element or NULL if the heap position i is free.

Definition at line 253 of file heap.c.

References Theap::data, and GetVectorElement().

Referenced by GetHeapElementWithID(), Heap2List(), HeapOfBoxesMaxDiagonal(), HeapOfBoxesMaxSize(), HeapOfBoxesVolume(), and PrintHeapOfBoxes().

Here is the call graph for this function:

Here is the caller graph for this function:

void* GetHeapElementWithID	(	unsigned int	id,
		Theap *	heap
	)

Returns a pointer to a heap element given the element identifier.

Parameters:

	id	The identifier of the object to retrive.
	heap	The heap to query.

Definition at line 262 of file heap.c.

References GetHeapElement(), GetHeapPosition(), and Theap::hasIDs.

Here is the call graph for this function:

unsigned int GetHeapPosition	(	unsigned int	id,
		Theap *	heap
	)

Returns the current position in the heap of an element given its identifier.

Parameters:

	id	The identifier of the object whose position is to be retrived.
	heap	The heap to query.

Definition at line 270 of file heap.c.

References GetVectorElement(), Theap::hasIDs, Theap::id2data, and NO_UINT.

Referenced by GetHeapElementWithID(), and UpdateHeapElement().

Here is the call graph for this function:

Here is the caller graph for this function:

void ExtractMinElement	(	void *	e,
		Theap *	heap
	)

Returns a pointer to a the minimal (i.e., the first) element of a heap and removes the element from the heap.

This function triggers an error if the heap is empty.

Parameters:

	e	Pointer to a space where to store the element to be extracted from the heap.
	heap	The heap to query and update.

Definition at line 278 of file heap.c.

References Theap::data, Theap::data2id, Error(), ExtractVectorElement(), GetVectorElement(), Theap::hasIDs, HeapDown(), Theap::id2data, Theap::last, RemoveVectorElement(), and SwapVectorElements().

Referenced by MPI_SolveCuikSystem(), and SolveCuikSystem().

Here is the call graph for this function:

Here is the caller graph for this function:

void ResetHeap ( Theap * heap )

Removes all the elements from a heap.

Parameters:

heap

The heap to reset.

Definition at line 304 of file heap.c.

References Theap::data, Theap::data2id, Theap::hasIDs, Theap::id2data, Theap::last, and ResetVector().

Referenced by DeleteHeap().

Here is the call graph for this function:

Here is the caller graph for this function:

void DeleteHeap ( Theap * heap )

Deletes the information stored in the heap and frees the allocated memory space.

Parameters:

heap

The heap to be deleted.

Definition at line 316 of file heap.c.

References Theap::data, Theap::data2id, DeleteVector(), Theap::hasIDs, Theap::id2data, and ResetHeap().

Referenced by MPI_SolveCuikSystem(), and SolveCuikSystem().

Here is the call graph for this function:

Here is the caller graph for this function:

heap.h File Reference

Data Structures

Functions

Detailed Description

Function Documentation