Suppose that you want to implement the priority_queue (the priority is stored in the node data field) so that insertions occur in constant time, but getting the front item requires linear time. You will use these class definitions:

class priority_queue

{ void push(const Item& entry);

value_type top( );

...

private: node *head_ptr;

}

(A)Write ONE sentence to describe how the push member function will work (with constant time). (10 points)

(B) Then implement the top function (which will have linear worst-case time). In your implementation, you DO NOT have to worry about items with equal priority (they may come out of the priority_queue however you like, without necessarily having FIFO behavior). You may also assume that the following two toolkit functions have been modified to work with the priority_queue's node: (10 points))

void list_head_remove(Node*& head_ptr); // Removes head node of a list

void list_remove(Node* precursor); // Removes node after *precursor