Mastering Algorithms With C - Kyle Loudon [108]
rpos = heap_right(ipos);
while (1) {
/**************************************************************************
* *
* Select the child to swap with the current node. *
* *
**************************************************************************/
lpos = heap_left(ipos);
rpos = heap_right(ipos);
if (lpos < heap_size(heap) && heap->compare(heap->tree[lpos], heap->
tree[ipos]) > 0) {
mpos = lpos;
}
else {
mpos = ipos;
}
if (rpos < heap_size(heap) && heap->compare(heap->tree[rpos], heap->
tree[mpos]) > 0) {
mpos = rpos;
}
/**************************************************************************
* *
* When mpos is ipos, the heap property has been restored. *
* *
**************************************************************************/
if (mpos == ipos) {
break;
}
else {
/***********************************************************************
* *
* Swap the contents of the current node and the selected child. *
* *
***********************************************************************/
temp = heap->tree[mpos];
heap->tree[mpos] = heap->tree[ipos];
heap->tree[ipos] = temp;
/***********************************************************************
* *
* Move down one level in the tree to continue heapifying. *
* *
***********************************************************************/
ipos = mpos;
}
}
return 0;
}
Description of Priority Queues
Priority queues are used to prioritize data. A priority queue consists of elements organized so that the highest priority element can be ascertained efficiently. For example, consider maintaining usage statistics about a number of servers for which you are trying to do load balancing. As connection requests arrive, a priority queue can be used to determine which server is best able to accommodate the new request. In this scenario, the server with least usage is the one that gets the highest priority because it is the best one to service the request.
Interface for Priority Queues
Name
pqueue_init
Synopsis
void pqueue_init(PQueue *pqueue, int (*compare)(const void *key1,
const void *key2), void (*destroy)(void *data));
Return Value
None.
Description
Initializes the priority queue specified by pqueue. This operation must be called for a priority queue before it can be used with any other operation. The compare argument is a function used by various priority queue operations in maintaining the priority queue's heap property. This function should return 1 if key1 > key2, if key1 = key2, and -1 if key1 < key2 for a priority queue in which large keys have a higher priority. For a priority queue in which smaller keys have a higher priority, compare should reverse the cases that return 1 and -1. The destroy argument provides a way to free dynamically allocated data when pqueue_destroy is called. For example, if the priority queue contains data dynamically allocated using malloc, destroy should be set to free to free the data as the priority queue 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 priority queue containing data that should not be freed, destroy should be set to NULL.
Complexity
O (1)
Name
pqueue_destroy
Synopsis
void pqueue_destroy(PQueue *pqueue);
Return Value
None.
Description
Destroys the priority queue specified by pqueue. No other operations are permitted after calling pqueue_destroy unless pqueue_init is called again. The pqueue_destroy operation extracts all elements from a priority queue and calls the function passed as destroy to pqueue_init once for each element as it is extracted, provided destroy was not set to NULL.
Complexity
O (n), where n is the number of elements in the priority queue.
Name
pqueue_insert
Synopsis
int pqueue_insert(PQueue *pqueue, const void *data);
Return Value
0if inserting the element is successful,