usual/heap.h File Reference

Binary heap. More...

Typedefs
typedef bool(*	heap_is_better_f )(const void *a, const void *b)
	Object comparision function.
typedef void(*	heap_save_pos_f )(void *a, unsigned pos)
	Heap position storage.
Functions
struct Heap *	heap_create (heap_is_better_f is_better_cb, heap_save_pos_f save_pos_cb, CxMem *cx)
	Create new heap object.
void	heap_destroy (struct Heap *h)
	Release memory allocated by heap.
bool	heap_push (struct Heap *h, void *ptr)
	Put new object into heap.
void *	heap_pop (struct Heap *h)
	Remove and return topmost object from heap.
void *	heap_top (struct Heap *h)
	Return topmost object in heap.
void *	heap_remove (struct Heap *h, unsigned pos)
	Remove and return any object from heap by index.
bool	heap_reserve (struct Heap *h, unsigned extra)
	Reserve room for more elements.
unsigned	heap_size (struct Heap *h)
	Return number of objects in heap.

---

Detailed Description

Binary heap.

Binary heap is sort of binary tree held inside array, with following 2 properties:

• heap property: each node is "better" than it's childs.
• shape property: binary tree is complete, meaning all levels except the last one are fully filled.

Instead of "min"- or "max"-heap, this is "best"-heap, as it operates with user-defined heap_is_better() functions, which is used to bubble elements on top.

---

Typedef Documentation

typedef bool(* heap_is_better_f)(const void *a, const void *b)

Object comparision function.

Should return true if a needs to reach top before b, false if not or equal.

typedef void(* heap_save_pos_f)(void *a, unsigned pos)

Heap position storage.

If user wants to delete elements from the middle of heap, this function should be used to keep track where the element is located.

---

Function Documentation

struct Heap* heap_create	(	heap_is_better_f	is_better_cb,
		heap_save_pos_f	save_pos_cb,
		CxMem *	cx
	)		[read]

Create new heap object.

Parameters:

is_better_cb	Callback to decide priority.
save_pos_cb	Callback to store current index.
cx	Allocation context.

void heap_destroy

(

struct Heap *

h

)

Release memory allocated by heap.

bool heap_push	(	struct Heap *	h,
		void *	ptr
	)

Put new object into heap.

void* heap_pop

(

struct Heap *

h

)

Remove and return topmost object from heap.

void* heap_top

(

struct Heap *

h

)

Return topmost object in heap.

void* heap_remove	(	struct Heap *	h,
		unsigned	pos
	)

Remove and return any object from heap by index.

bool heap_reserve	(	struct Heap *	h,
		unsigned	extra
	)

Reserve room for more elements.

Returns false if allocation failed.

unsigned heap_size

(

struct Heap *

h

)

Return number of objects in heap.