• Choose a category
• All
• Classic-Fiction

By Root 1611 0

swap is required, or we reach a leaf node. Last, we update the size of the heap by decreasing the size member of the heap data structure by 1.

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

heap_size

This macro evaluates to the number of nodes in a heap (see Example 10.1). It works by accessing the size member of the Heap structure.

Figure 10.3. Extracting 25 from a top-heavy heap

The runtime complexity of heap_size is O (1) because accessing a member of a structure is a simple task that runs in a constant amount of time.

Example 10.2. Implementation of the Heap Abstract Datatype

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

* *

* -------------------------------- heap.c -------------------------------- *

* *

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

#include

#include

#include "heap.h"

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

* *

* Define private macros used by the heap implementation. *

* *

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

#define heap_parent(npos) ((int)(((npos) - 1) / 2))

#define heap_left(npos) (((npos) * 2) + 1)

#define heap_right(npos) (((npos) * 2) + 2)

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

* *

* ------------------------------- heap_init ------------------------------ *

* *

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

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

void (*destroy)(void *data)) {

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

* *

* Initialize the heap. *

* *

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

heap->size = 0;

heap->compare = compare;

heap->destroy = destroy;

heap->tree = NULL;

return;

}

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

* *

* ----------------------------- heap_destroy ----------------------------- *

* *

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

void heap_destroy(Heap *heap) {

int i;

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

* *

* Remove all the nodes from the heap. *

* *

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

if (heap->destroy != NULL) {

for (i = 0; i < heap_size(heap); i++) {

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

* *

* Call a user-defined function to free dynamically allocated data. *

* *

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

heap->destroy(heap->tree[i]);

}

}

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

* *

* Free the storage allocated for the heap. *

* *

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

free(heap->tree);

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

* *

* No operations are allowed now, but clear the structure as a precaution. *

* *

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

memset(heap, 0, sizeof(Heap));

return;

}

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

* *

* ------------------------------ heap_insert ----------------------------- *

* *

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

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

void *temp;

int ipos,

ppos;

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

* *

* Allocate storage for the node. *

*