ScalES-PPM
Loading...
Searching...
No Matches
heap.h File Reference

routines for sorting arrays into binary heap order More...

#include <stdlib.h>
#include "core/fptr_api.h"

Functions

void PPM_heapify (void *heap, size_t n, size_t es, size_t i, void *data, PPM_CompareWithData cmp)
 restore binary heap property for sub-tree starting at i This function assumes that the heap property is fulfilled for all child trees of i.
 
void PPM_build_heap (void *heap, size_t n, size_t es, void *data, PPM_CompareWithData cmp)
 restore binary heap property for sub-tree starting at i
 
int PPM_is_heap (void *heap, size_t n, size_t es, void *data, PPM_CompareWithData cmp)
 check whether array fulfills binary heap property
 
void PPM_heap_remove_top (void *heap, size_t n, size_t es, void *data, PPM_CompareWithData cmp)
 remove heap top by replacing with leaf and restore heap property
 
void PPM_heap_elem_increase_sort (void *heap, size_t n, size_t es, size_t i, void *data, PPM_CompareWithData cmp)
 restore heap property after increasing sort of single element i of heap
 
void PPM_heap_leaf_minimize (void *heap, size_t n, size_t es, void *data, PPM_CompareWithData cmp)
 rearrange leafs such that last element is also lowest sorting
 

Detailed Description

routines for sorting arrays into binary heap order

Version
1.0
Author
Thomas Jahns jahns.nosp@m.@dkr.nosp@m.z.de

Function Documentation

◆ PPM_build_heap()

void PPM_build_heap ( void * heap,
size_t n,
size_t es,
void * data,
PPM_CompareWithData cmp )

restore binary heap property for sub-tree starting at i

Parameters
heappointer to base address of array
essize of element
nnumber of elements in array
datapointer to arbitrary data used by cmp
cmpcomparison function

◆ PPM_heap_elem_increase_sort()

void PPM_heap_elem_increase_sort ( void * heap,
size_t n,
size_t es,
size_t i,
void * data,
PPM_CompareWithData cmp )

restore heap property after increasing sort of single element i of heap

Parameters
heappointer to base address of array
essize of element
nnumber of elements in array
imodified element (multiplied with es to compute offset)
datapointer to arbitrary data used by cmp
cmpcomparison function

◆ PPM_heap_leaf_minimize()

void PPM_heap_leaf_minimize ( void * heap,
size_t n,
size_t es,
void * data,
PPM_CompareWithData cmp )

rearrange leafs such that last element is also lowest sorting

Parameters
heappointer to base address of array
essize of element
nnumber of elements in array
datapointer to arbitrary data used by cmp
cmpcomparison function

◆ PPM_heap_remove_top()

void PPM_heap_remove_top ( void * heap,
size_t n,
size_t es,
void * data,
PPM_CompareWithData cmp )

remove heap top by replacing with leaf and restore heap property

Parameters
heappointer to base address of array
essize of element
nnumber of elements in array
datapointer to arbitrary data used by cmp
cmpcomparison function

◆ PPM_heapify()

void PPM_heapify ( void * heap,
size_t n,
size_t es,
size_t i,
void * data,
PPM_CompareWithData cmp )

restore binary heap property for sub-tree starting at i This function assumes that the heap property is fulfilled for all child trees of i.

Parameters
heappointer to base address of array
essize of element
nnumber of elements in array
istart element (multiplied with es to compute offset)
datapointer to arbitrary data used by cmp
cmpcomparison function

◆ PPM_is_heap()

int PPM_is_heap ( void * heap,
size_t n,
size_t es,
void * data,
PPM_CompareWithData cmp )

check whether array fulfills binary heap property

Parameters
heappointer to base address of array
essize of element
nnumber of elements in array
datapointer to arbitrary data used by cmp
cmpcomparison function
Returns
0 if heap does not fulfill heap property, non-zero otherwise

Das diesem Bericht zugrundeliegende Vorhaben wurde mit Mitteln des Bundesministeriums für Bildung, und Forschung unter dem Förderkennzeichen 01IH08004E gefördert. Die Verantwortung für den Inhalt dieser Veröffentlichung liegt beim Autor.