binomial-heap.h File Reference

The cdc_binomial_heap is a struct and functions that provide a binomial heap. More...

#include <cdcontainers/common.h>
#include <cdcontainers/status.h>
#include <assert.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdlib.h>

Go to the source code of this file.

Data Structures
struct	cdc_binomial_heap_node
	The cdc_binomial_heap_node struct. More...
struct	cdc_binomial_heap
	The cdc_binomial_heap struct. More...
struct	cdc_binomial_heap_iter
	The cdc_binomial_heap_iter struct. More...

Functions
enum cdc_stat	cdc_binomial_heap_ctor (struct cdc_binomial_heap **h, struct cdc_data_info *info)
	Constructs an empty binomial heap. More...
enum cdc_stat	cdc_binomial_heap_ctorl (struct cdc_binomial_heap **h, struct cdc_data_info *info,...)
	Constructs a binomial heap, initialized by an arbitrary number of pointers. The last item must be NULL. More...
enum cdc_stat	cdc_binomial_heap_ctorv (struct cdc_binomial_heap **h, struct cdc_data_info *info, va_list args)
	Constructs a binomial heap, initialized by args. The last item must be NULL. More...
void	cdc_binomial_heap_dtor (struct cdc_binomial_heap *h)
	Destroys the binomial heap. More...
static void *	cdc_binomial_heap_top (struct cdc_binomial_heap *h)
	Returns a pointer to the binomial heap's top item. This function assumes that the binomial heap isn't empty. More...
static size_t	cdc_binomial_heap_size (struct cdc_binomial_heap *h)
	Returns the number of items in the binomial heap. More...
static bool	cdc_binomial_heap_empty (struct cdc_binomial_heap *h)
	Returns true if the binomial heap has size 0; otherwise returns false. More...
enum cdc_stat	cdc_binomial_heap_extract_top (struct cdc_binomial_heap *h)
	Extracts the top item from the binomial heap. This function assumes that the binomial heap isn't empty. More...
enum cdc_stat	cdc_binomial_heap_riinsert (struct cdc_binomial_heap *h, void *key, struct cdc_binomial_heap_iter *ret)
	Inserts element key to the binomial heap. Write an iterator pointing to a new element in the ret. More...
static enum cdc_stat	cdc_binomial_heap_insert (struct cdc_binomial_heap *h, void *key)
	Inserts element key to the binomial heap. More...
void	cdc_binomial_heap_change_key (struct cdc_binomial_heap *h, struct cdc_binomial_heap_iter *pos, void *key)
	Changes the item key on the pos position in the binomial heap. More...
void	cdc_binomial_heap_clear (struct cdc_binomial_heap *h)
	Removes all the elements from the binomial heap. More...
void	cdc_binomial_heap_swap (struct cdc_binomial_heap *a, struct cdc_binomial_heap *b)
	Swaps binomial heaps a and b. This operation is very fast and never fails. More...
void	cdc_binomial_heap_merge (struct cdc_binomial_heap *h, struct cdc_binomial_heap *other)
	Merges two heaps. In the heap h will be the result of the merger, and the heap other will remain empty. More...
bool	cdc_binomial_heap_is_heap (struct cdc_binomial_heap *h)
	Checks the heap property. More...
static void *	cdc_binomial_heap_iter_data (struct cdc_binomial_heap_iter *it)
	Returns a pointer to the key of current item. More...
static bool	cdc_binomial_heap_iter_is_eq (struct cdc_binomial_heap_iter *it1, struct cdc_binomial_heap_iter *it2)
	Returns false if the iterator it1 equal to the iterator it2, otherwise returns false. More...

Detailed Description

The cdc_binomial_heap is a struct and functions that provide a binomial heap.

Author

Maksim Andrianov maksi.nosp@m.mand.nosp@m.riano.nosp@m.v1@y.nosp@m.andex.nosp@m..ru

Function Documentation

cdc_binomial_heap_ctor()

enum cdc_stat cdc_binomial_heap_ctor	(	struct cdc_binomial_heap **	h,
		struct cdc_data_info *	info
	)

Constructs an empty binomial heap.

Parameters

h	- cdc_binomial_heap
info	- cdc_data_info

Returns

CDC_STATUS_OK in a successful case or other value indicating an error

cdc_binomial_heap_ctorl()

enum cdc_stat cdc_binomial_heap_ctorl	(	struct cdc_binomial_heap **	h,
		struct cdc_data_info *	info,
			...
	)

Constructs a binomial heap, initialized by an arbitrary number of pointers. The last item must be NULL.

Parameters

h	- cdc_binomial_heap
info	- cdc_data_info

Returns

CDC_STATUS_OK in a successful case or other value indicating an error

cdc_binomial_heap_ctorv()

enum cdc_stat cdc_binomial_heap_ctorv	(	struct cdc_binomial_heap **	h,
		struct cdc_data_info *	info,
		va_list	args
	)

Constructs a binomial heap, initialized by args. The last item must be NULL.

Parameters

h	- cdc_binomial_heap
info	- cdc_data_info

Returns

CDC_STATUS_OK in a successful case or other value indicating an error

cdc_binomial_heap_dtor()

void cdc_binomial_heap_dtor

(

struct cdc_binomial_heap *

h

)

Destroys the binomial heap.

Parameters

h	- cdc_binomial_heap

cdc_binomial_heap_top()

static void* cdc_binomial_heap_top ( struct cdc_binomial_heap *  h )

inlinestatic

Returns a pointer to the binomial heap's top item. This function assumes that the binomial heap isn't empty.

Parameters

h	- cdc_binomial_heap

Returns

top item

cdc_binomial_heap_size()

static size_t cdc_binomial_heap_size ( struct cdc_binomial_heap *  h )

inlinestatic

Returns the number of items in the binomial heap.

Parameters

h	- cdc_binomial_heap

Returns

size

cdc_binomial_heap_empty()

static bool cdc_binomial_heap_empty ( struct cdc_binomial_heap *  h )

inlinestatic

Returns true if the binomial heap has size 0; otherwise returns false.

Parameters

h	- cdc_binomial_heap

Returns

true if the binomial heap has size 0; otherwise returns false

cdc_binomial_heap_extract_top()

enum cdc_stat cdc_binomial_heap_extract_top

(

struct cdc_binomial_heap *

h

)

Extracts the top item from the binomial heap. This function assumes that the binomial heap isn't empty.

Parameters

h	- cdc_binomial_heap

Returns

CDC_STATUS_OK in a successful case or other value indicating an error

cdc_binomial_heap_riinsert()

enum cdc_stat cdc_binomial_heap_riinsert	(	struct cdc_binomial_heap *	h,
		void *	key,
		struct cdc_binomial_heap_iter *	ret
	)

Inserts element key to the binomial heap. Write an iterator pointing to a new element in the ret.

Parameters

h	- cdc_binomial_heap
key
ret	- pointer to iterator where an iterator will be written indicating the inserted element

Returns

CDC_STATUS_OK in a successful case or other value indicating an error

cdc_binomial_heap_insert()

static enum cdc_stat cdc_binomial_heap_insert ( struct cdc_binomial_heap *  h, void *  key  )

inlinestatic

Inserts element key to the binomial heap.

Parameters

h	- cdc_binomial_heap
key

Returns

CDC_STATUS_OK in a successful case or other value indicating an error

cdc_binomial_heap_change_key()

void cdc_binomial_heap_change_key	(	struct cdc_binomial_heap *	h,
		struct cdc_binomial_heap_iter *	pos,
		void *	key
	)

Changes the item key on the pos position in the binomial heap.

Parameters

h	- cdc_binomial_heap
pos	- iterator that indicates the item with key that you want to change
key

cdc_binomial_heap_clear()

void cdc_binomial_heap_clear

(

struct cdc_binomial_heap *

h

)

Removes all the elements from the binomial heap.

Parameters

h	- cdc_binomial_heap

cdc_binomial_heap_swap()

void cdc_binomial_heap_swap	(	struct cdc_binomial_heap *	a,
		struct cdc_binomial_heap *	b
	)

Swaps binomial heaps a and b. This operation is very fast and never fails.

Parameters

a	- cdc_binomial_heap
b	- cdc_binomial_heap

cdc_binomial_heap_merge()

void cdc_binomial_heap_merge	(	struct cdc_binomial_heap *	h,
		struct cdc_binomial_heap *	other
	)

Merges two heaps. In the heap h will be the result of the merger, and the heap other will remain empty.

Parameters

h	- cdc_binomial_heap
other	- cdc_binomial_heap

cdc_binomial_heap_is_heap()

bool cdc_binomial_heap_is_heap

(

struct cdc_binomial_heap *

h

)

Checks the heap property.

Parameters

h	- cdc_binomial_heap

Returns

result of the check

cdc_binomial_heap_iter_data()

static void* cdc_binomial_heap_iter_data ( struct cdc_binomial_heap_iter *  it )

inlinestatic

Returns a pointer to the key of current item.

cdc_binomial_heap_iter_is_eq()

static bool cdc_binomial_heap_iter_is_eq ( struct cdc_binomial_heap_iter *  it1, struct cdc_binomial_heap_iter *  it2  )

inlinestatic

Returns false if the iterator it1 equal to the iterator it2, otherwise returns false.