Explore BrainMass

Explore BrainMass

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

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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)

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

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

    delete header;

    © BrainMass Inc. brainmass.com December 15, 2022, 8:03 pm ad1c9bdddf

    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.