Heap

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)