• Choose a category
• All
• Classic-Fiction

#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 heap_extract(Heap *heap, void **data);

#define heap_size(heap) ((heap)->size)

#endif

heap_init

The heap_init operation initializes a heap so that it can be used in other operations (see Example 10.2). Initializing a heap is a simple operation in which we set the size member of the heap to 0, the destroy member to destroy, and the tree pointer to NULL.

The runtime complexity of heap_init is O (1) because all of the steps in initializing a heap run in a constant amount of time.

heap_destroy

The heap_destroy operation destroys a heap (see Example 10.2). Primarily this means removing all nodes from the heap. The function passed as destroy to heap_init is called once for each node as it is removed, provided destroy was not set to NULL.

The runtime complexity of heap_destroy is O (n), where n is the number of nodes in the heap. This is because we must traverse all nodes in the heap in order to free the data they contain. If destroy is NULL, heap_destroy runs in O (1) time.

heap_insert

The heap_insert operation inserts a node into a heap (see Example 10.2). The call sets the new node to point to the data passed by the caller. To begin, we reallocate storage to enable the tree to accommodate the new node. The actual process of inserting the new node initially places it into the last position in the array. When this causes the heap property to be violated, we must reheapify the tree (see Figure 10.2).

Figure 10.2. Inserting 24 into a top-heavy heap

To reheapify a tree after inserting a node, we need only consider the branch in which the new node has been inserted, since the tree was a heap to begin with. Starting at the new node, we move up the tree level by level, comparing each child with its parent. At each level, if a parent and child are in the wrong order, we swap their contents. This process continues until we reach a level at which no swap is required, or we reach the top of the tree. Last, we update the size of the heap by incrementing the size member of the heap data structure.

The runtime complexity of heap_insert is O (lg n), where n is the number of nodes in the tree. This is because heapification requires moving the contents of the new node from the lowest level of the tree to the top in the worst case, a traversal of lg n levels. All other parts of the operation run in a constant amount of time.

heap_extract

The heap_extract operation extracts the node at the top of a heap (see Example 10.2). To begin, we set data to point to the data stored in the node being extracted. Next, we save the contents of the last node, reallocate a smaller amount of storage for the tree, and decrease the tree size by 1. After we are certain this has succeeded, we copy the contents of the saved last node to the root node. When this causes the heap property to be violated, we must reheapify the tree (see Figure 10.3).

To reheapify a tree after extracting a node, we start at the root node and move down the tree level by level, comparing each node with its two children. At each level, if a parent and its children are in the wrong order, we swap their contents and move to the child that was the most out of order. This process continues until we reach a level at which no