Suppose that you want to implement the priority_queue so that insertions occur i

Question

Suppose that you want to implement the priority_queue so that insertions occur in constant time, but getting the front item requires linear time. You will use these class definitions:

template

    class priority_queue

    {

        typedef Item value_type;

        void push(const Item&x entry);

        value_type top( );

        ...

    private:

        node *head_ptr;

    };

Write ONE sentence to describe how the insert member function will work (with constant time).

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 prioirty queue however you like, without necessarily having FIFO behavior). You may also assume that these two toolkit functions have been modified to work with the priority_queue's node:

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

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

Explanation / Answer

Inserting...

In single line.....Node newnode = new Node();

newnode.item = some value.

void list_head_remove(Node*& head_ptr){

head_ptr.prev = null; //It will make next node as header node

remove(head_ptr); //it will remove node

}

void list_remove(Node* precursor){

precursor.prev.next = precursor.next; // here setting previous node next link as immediate next link node

remove(precursor); // removing Node

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.