• Choose a category
• All
• Classic-Fiction

By Root 1464 0

9). Assuming a zero-indexed array, this means that the parent of each node at some position i in the array is located at position └(i - 1)/2┘, where └ ┘ means to ignore the fractional part of (i - 1)/2. The left and right children of a node are located at positions 2i + 1 and 2i + 2. This organization is especially important for heaps because it allows us to locate a heap's last node quickly: the last node is the rightmost node at the deepest level. This is important in implementing certain heap operations.

Figure 10.1. A top-heavy heap (a) conceptually and (b) represented in an array

Interface for Heaps

Name

heap_init

Synopsis

void heap_init(Heap *heap, int (*compare)(const void *key1, const void *key2)

void (*destroy)(void *data));

Return Value

None.

Description

Initializes the heap specified by heap. This operation must be called for a heap before the heap can be used with any other operation. The compare argument is a function used by various heap operations to compare nodes when fixing the heap. This function should return 1 if key1 > key2, if key1 = key2, and -1 if key1 < key2 for a top-heavy heap. For a bottom-heavy heap, compare should reverse the cases that return 1 and -1. The destroy argument provides a way to free dynamically allocated data when heap_destroy is called. For example, if the heap contains data dynamically allocated using malloc, destroy should be set to free to free the data as the heap is destroyed. For structured data containing several dynamically allocated members, destroy should be set to a user-defined function that calls free for each dynamically allocated member as well as for the structure itself. For a heap containing data that should not be freed, destroy should be set to NULL.

Complexity

O (1)

Name

heap_destroy

Synopsis

void heap_destroy(Heap *heap);

Return Value

None.

Description

Destroys the heap specified by heap. No other operations are permitted after calling heap_destroy unless heap_init is called again. The heap_destroy operation removes all nodes from a heap and calls the function passed as destroy to heap_init once for each node as it is removed, provided destroy was not set to NULL.

Complexity

O (n), where n is the number of nodes in the heap.

Name

heap_insert

Synopsis

int heap_insert(Heap *heap, const void *data);

Return Value

0if inserting the node is successful, or -1 otherwise.

Description

Inserts a node into the heap specified by heap. The new node contains a pointer to data, so the memory referenced by data should remain valid as long as the node remains in the heap. It is the responsibility of the caller to manage the storage associated with data.

Complexity

O (lg n), where n is the number of nodes in the heap.

Name

heap_extract

Synopsis

int heap_extract(Heap *heap, void **data);

Return Value

0if extracting the node is successful, or -1 otherwise.

Description

Extracts the node at the top of the heap specified by heap. Upon return, data points to the data stored in the node that was extracted. It is the responsibility of the caller to manage the storage associated with the data.

Complexity

O (lg n), where n is the number of nodes in the heap.

Name

heap_size

Synopsis

int heap_size(const Heap *heap);

Return Value

Number of nodes in the heap.

Description

Macro that evaluates to the number of nodes in the heap specified by heap.

Complexity

O (1)

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 -------------------------------- *

* *

*****************************************************************************/