routines for sorting arrays into binary heap order
More...
#include <assert.h>
#include <stddef.h>
#include <stdlib.h>
#include "core/heap.h"
#include "core/ppm_visibility.h"
#include "core/fptr_api.h"
#include "core/swapmacros.h"
|
#define | ep(i) ((unsigned char *)heap + (i) * es) |
|
|
void PPM_DSO_API_EXPORT | 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.
|
|
int PPM_DSO_API_EXPORT | 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_DSO_API_EXPORT | 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
|
|
void PPM_DSO_API_EXPORT | 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_DSO_API_EXPORT | 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_DSO_API_EXPORT | 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
|
|
routines for sorting arrays into binary heap order
- Copyright
- Copyright (C) 2012 Thomas Jahns jahns.nosp@m.@dkr.nosp@m.z.de
- Version
- 1.0
- Author
- Thomas Jahns jahns.nosp@m.@dkr.nosp@m.z.de
◆ PPM_build_heap()
void PPM_DSO_API_EXPORT 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
-
heap | pointer to base address of array |
es | size of element |
n | number of elements in array |
data | pointer to arbitrary data used by cmp |
cmp | comparison function |
◆ PPM_heap_elem_increase_sort()
void PPM_DSO_API_EXPORT 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
-
heap | pointer to base address of array |
es | size of element |
n | number of elements in array |
i | modified element (multiplied with es to compute offset) |
data | pointer to arbitrary data used by cmp |
cmp | comparison function |
◆ PPM_heap_leaf_minimize()
void PPM_DSO_API_EXPORT 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
-
heap | pointer to base address of array |
es | size of element |
n | number of elements in array |
data | pointer to arbitrary data used by cmp |
cmp | comparison function |
◆ PPM_heap_remove_top()
void PPM_DSO_API_EXPORT 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
-
heap | pointer to base address of array |
es | size of element |
n | number of elements in array |
data | pointer to arbitrary data used by cmp |
cmp | comparison function |
◆ PPM_heapify()
void PPM_DSO_API_EXPORT 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
-
heap | pointer to base address of array |
es | size of element |
n | number of elements in array |
i | start element (multiplied with es to compute offset) |
data | pointer to arbitrary data used by cmp |
cmp | comparison function |
◆ PPM_is_heap()
int PPM_DSO_API_EXPORT PPM_is_heap |
( |
void * | heap, |
|
|
size_t | n, |
|
|
size_t | es, |
|
|
void * | data, |
|
|
PPM_CompareWithData | cmp ) |
check whether array fulfills binary heap property
- Parameters
-
heap | pointer to base address of array |
es | size of element |
n | number of elements in array |
data | pointer to arbitrary data used by cmp |
cmp | comparison 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.