Mastering Algorithms With C - Kyle Loudon [107]
*****************************************************************************/
if ((temp = (void **)realloc(heap->tree, (heap_size(heap) + 1) * sizeof
(void *))) == NULL) {
return -1;
}
else {
heap->tree = temp;
}
/*****************************************************************************
* *
* Insert the node after the last node. *
* *
*****************************************************************************/
heap->tree[heap_size(heap)] = (void *)data;
/*****************************************************************************
* *
* Heapify the tree by pushing the contents of the new node upward. *
* *
*****************************************************************************/
ipos = heap_size(heap);
ppos = heap_parent(ipos);
while (ipos > 0 && heap->compare(heap->tree[ppos], heap->tree[ipos]) < 0) {
/**************************************************************************
* *
* Swap the contents of the current node and its parent. *
* *
**************************************************************************/
temp = heap->tree[ppos];
heap->tree[ppos] = heap->tree[ipos];
heap->tree[ipos] = temp;
/**************************************************************************
* *
* Move up one level in the tree to continue heapifying. *
* *
**************************************************************************/
ipos = ppos;
ppos = heap_parent(ipos);
}
/*****************************************************************************
* *
* Adjust the size of the heap to account for the inserted node. *
* *
*****************************************************************************/
heap->size++;
return 0;
}
/*****************************************************************************
* *
* ----------------------------- heap_extract ----------------------------- *
* *
*****************************************************************************/
int heap_extract(Heap *heap, void **data) {
void *save,
*temp;
int ipos,
lpos,
rpos,
mpos;
/*****************************************************************************
* *
* Do not allow extraction from an empty heap. *
* *
*****************************************************************************/
if (heap_size(heap) == 0)
return -1;
/*****************************************************************************
* *
* Extract the node at the top of the heap. *
* *
*****************************************************************************/
*data = heap->tree[0];
/*****************************************************************************
* *
* Adjust the storage used by the heap. *
* *
*****************************************************************************/
save = heap->tree[heap_size(heap) - 1];
if (heap_size(heap) - 1 > 0) {
if ((temp = (void **)realloc(heap->tree, (heap_size(heap) - 1) * sizeof
(void *))) == NULL) {
return -1;
}
else {
heap->tree = temp;
}
/**************************************************************************
* *
* Adjust the size of the heap to account for the extracted node. *
* *
**************************************************************************/
heap->size--;
}
else {
/**************************************************************************
* *
* Manage the heap when extracting the last node. *
* *
**************************************************************************/
free(heap->tree);
heap->tree = NULL;
heap->size = 0;
return 0;
}
/*****************************************************************************
* *
* Copy the last node to the top. *
* *
*****************************************************************************/
heap->tree[0] = save;
/*****************************************************************************
* *
* Heapify the tree by pushing the contents of the new top downward. *
* *
*****************************************************************************/
ipos = 0;
lpos =