class Heap


Public Methods

Heap(int size=HEAP_DEFAULT_SIZE)
int heap_delete(void* elem)
int heap_delete(Heap *h, void *elem): O(n) algorithm

Returns 1 for success, 0 otherwise

void* heap_extract_min()
void *heap_extract_min(Heap *h)

Returns the smallest element in the heap, if it exists

void heap_insert(heap_key_t key, void* elem)
void heap_insert(Heap *h, heap_key_t *key, void *elem)

Insert <key, elem> into heap h

void* heap_iter()
void* heap_iter_init()
Couple of functions to support iterating through all things on the heap without having to know what a heap looks like
int heap_member(void* elem)
int heap_member(Heap *h, void *elem): O(n) algorithm
void* heap_min()
void *heap_min(Heap *h)

Returns the smallest element in the heap, if it exists, NULL otherwise

~Heap()

Private Fields

unsigned int h_iter
unsigned int h_maxsize
unsigned int h_s_key
unsigned int h_size

Private Methods

unsigned int KEY_LESS_OR_EQUAL_THAN(heap_key_t k1, heap_key_t k2)
unsigned int KEY_LESS_THAN(heap_key_t k1, heap_secondary_key_t ks1, heap_key_t k2, heap_secondary_key_t ks2)
unsigned int left(unsigned int i)
unsigned int parent(unsigned int i)
unsigned int right(unsigned int i)
void swap(unsigned int i, unsigned int j)

Private

struct Heap_elem
heap_key_t he_key
heap_secondary_key_t he_s_key
void* he_elem

Documentation

struct Heap_elem

heap_key_t he_key

heap_secondary_key_t he_s_key

void* he_elem

unsigned int h_s_key

unsigned int h_size

unsigned int h_maxsize

unsigned int h_iter

unsigned int parent(unsigned int i)

unsigned int left(unsigned int i)

unsigned int right(unsigned int i)

void swap(unsigned int i, unsigned int j)

unsigned int KEY_LESS_THAN(heap_key_t k1, heap_secondary_key_t ks1, heap_key_t k2, heap_secondary_key_t ks2)

unsigned int KEY_LESS_OR_EQUAL_THAN(heap_key_t k1, heap_key_t k2)

Heap(int size=HEAP_DEFAULT_SIZE)

~Heap()

int heap_member(void* elem)
int heap_member(Heap *h, void *elem): O(n) algorithm

int heap_delete(void* elem)
int heap_delete(Heap *h, void *elem): O(n) algorithm

Returns 1 for success, 0 otherwise

void* heap_iter_init()
Couple of functions to support iterating through all things on the heap without having to know what a heap looks like. To be used as follows:

for (elem = heap_iter_init(h); elem; elem = heap_iter(h)) Do whatever to the elem.

You cannot use heap_iter to do anything but inspect the heap. If heap_insert(), heap_extract_min(), or heap_delete() are called while iterating through the heap, all bets are off.

Tue Nov 14 20:17:59 PST 1995 -- kva Actually now, heap_create() initialises h_iter correctly, and heap_iter() correctly resets h_iter when the heap is traversed, So, we do not really need heap_iter_init() anymore, except to break off a current iteration and restart.

void* heap_iter()

void heap_insert(heap_key_t key, void* elem)
void heap_insert(Heap *h, heap_key_t *key, void *elem)

Insert <key, elem> into heap h. Adjust heap_size if we hit the limit.

void* heap_min()
void *heap_min(Heap *h)

Returns the smallest element in the heap, if it exists, NULL otherwise. The element is still in the heap.

void* heap_extract_min()
void *heap_extract_min(Heap *h)

Returns the smallest element in the heap, if it exists. NULL otherwise.


This class has no child classes.

alphabetic index hierarchy of classes


this page has been generated automatically by doc++

Adapted for the NS documentation page

(c)opyright by Malte Zöckler, Roland Wunderling
contact: doc++@zib.de