How to implemet priority queue data structure for the addition of two polynomial expression?

Question

1.00/5 (1 vote)

See more:

Hello. I have to make a project for school. My task is to choose a data structure for the addition of two polynomial expression, with high exponents and lots of null coefficients. I made my program using linked list data structure, but my teacher told my that linked list is not as efficient as the priority queue data structure in this case. Can somebody give me a clue how to implement a priority queue for the addition of two polynomial expression using c++ language? Are there more efficient data structure for my project?

What I have tried:

My program is based on the linked list data structure.

Posted 6-Jun-16 3:51am

Member 12530538

Updated 6-Jun-16 6:08am

Add a Solution

2 solutions

Solution 1

See priority queue data structure - Google Search[^].

Posted 6-Jun-16 3:53am

Richard MacCutchan

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Accepted Answer · 2016-06-06T06:08:00

Solution 2

Are you really sure you need to implement priority queue, not just use available one?

Priority queue is already implemented in a C++ standard library, std::priority_queue:
priority_queue — C++ Reference.

—SA

Posted 6-Jun-16 6:08am

Sergey Alexandrovich Kryukov

Comments

Member 12530538 7-Jun-16 6:18am

Yes I can use std::priority_queue. This could be my solution. But why using priority queue is more efficient for the addition of two polynomial expression that using linked list?

Sergey Alexandrovich Kryukov 7-Jun-16 9:48am

You did not ask about it, so I did not think about it. I'm not sure I understand the ultimate goals of your project.
It is CAS, expression parser, interpreter, anything else?
—SA

Member 12530538 7-Jun-16 14:27pm

Sorry but i don't understand your question. The main goal of my project is to choose between a data structure and implement it for the addition of two polynomial expressions. First, I have choosen linked list data structure but my teacher told my that is not efficient(because the of the usage of too many 'while' and 'if' statements). She recently told me that I should use priority queue for my program, but I can't understand how priority queue could help me to complete my project. Could you give me a clue on how to use priority queue in my project ? Or maybe you know another data structure better...

Sergey Alexandrovich Kryukov 7-Jun-16 14:32pm

Sorry, no, the purpose of the project could not be the choice between some structure. First of all, the project should be complete and meet certain functionality requirements. And those requirements are formulated to reach some ultimate goals. What goals? The answer to your question may heavily depend on that.

Yes, the explanation of your teacher is basically correct. What's not clear about it? Keep asking your teacher. It will give you a good habit of not doing anything blind-folded. Yes, you already demonstrate right attitude. You really need to understand the purpose of what you are doing. From the other hand, it's not good that you cannot really formulate the purpose and the goals of your project.

The idea is: priority queue already sorts the data in a ways suitable to the way you need to use this data. It is done according to the class Compare you should supply as a generic parameter. Let's say, you group polynomial factors according the the degrees of the variable; in this case, your Compare predicate less should return the result of comparison by degree. And so on... Look at the description of the template class std::priority_queue and you will see.

Does it give you the idea now? Will you accept my answer formally.

—SA

Member 12530538 7-Jun-16 15:22pm

Thank you for the response. Yes it really help me. Now I understand why I should use a priority queue functionality.

Sergey Alexandrovich Kryukov 7-Jun-16 16:00pm

Oh, great. You are very welcome.
Good luck, call again.
—SA