Mastering Algorithms with C

Implementation and Analysis of Heaps

The heap implemented here is a binary tree whose nodes are arranged hierarchically in an array. The structure Heap is the heap data structure (see Example 10.1). This structure consists of four members: size is the number of nodes in the heap, compare and destroy are members used to encapsulate the functions passed to heap_init, and tree is the array of nodes in the heap.

Example 10.1. Header for the Heap Abstract Datatype

/***************************************************************************** * * * -------------------------------- heap.h -------------------------------- * * * *****************************************************************************/ #ifndef HEAP_H #define HEAP_H /***************************************************************************** * * * Define a structure for heaps. * * * *****************************************************************************/ typedef struct Heap_ { int size; int (*compare)(const void *key1, const void *key2); void (*destroy)(void *data); void **tree; } Heap; /***************************************************************************** * * * --------------------------- Public Interface --------------------------- * * * *****************************************************************************/ void heap_init(Heap *heap, int (*compare)(const void *key1, const void *key2), void (*destroy)(void *data)); void heap_destroy(Heap *heap); int heap_insert(Heap *heap, const void *data); int ...