Share
Explore BrainMass

C++: Delete largest value from the list (priority queue)

Assume that a doubly linked list "header" stores the elements of a priority queue. Implement the function pop(), which deletes the element with the largest value from the list (priority queue).

template < typename T >
void pop(dnode< T > *header);

Here is my best Guess at the problem!

{
if ( header->next = = header)
return;

dnode< T > *prevNode = header->prev, *succNode = header->next;

prevNode->next = succNode;
succNode->prev = prevNode;

delete header;
}

Solution Preview

If you are maintaining priority queue sorted in descending order then the largest value will be in the header node (assuming doubly linked list is non-empty). In that case logic for pop function will be like as you have already guessed in right direction.

{
dnode < T > *newHeader; // Useful, in case header is passed by reference and you want changes to be reflected back.

if (header == NULL) // This signifies empty ...

Solution Summary

This solution is more of a guidance. Solution first gives an implementation (function body) considering that the priority queue is maintained sorted in descending order. Then it considers that case that the priority queue is maintained sorted in ascending order and indicates what modification should be made to function body for descending case.

$2.19