473,320 Members | 1,879 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Priority queue based on a sorted linked list

I want to implement a priority queue based on a sorted linked list. The remove operation on the priority queue should remove the item with a smallest key. Can anybody give me an idea how to do that?
May 18 '08 #1
3 6926
Laharl
849 Expert 512MB
Well...Java has a PriorityQueue class builtin that derives from LinkedList...unless this is an academic excercise, in which case you need to work out how to sort a linked list even remotely efficiently. I recommend a variation on Selection Sort, though swapping is a little more complicated than it would be in an array. Once sorted, the smallest item should be the front node.
May 18 '08 #2
BigDaddyLH
1,216 Expert 1GB
Well...Java has a PriorityQueue class builtin that derives from LinkedList...
Really? java.util.PriorityQueue is "An unbounded priority queue based on a priority heap". The heap data structure make much more sense than a linked list. Why use a linked list in the first place?
May 18 '08 #3
Laharl
849 Expert 512MB
Really? java.util.PriorityQueue is "An unbounded priority queue based on a priority heap". The heap data structure make much more sense than a linked list. Why use a linked list in the first place?
That's what I get for going off memory rather than looking at the API...;)
May 18 '08 #4

Sign in to post your reply or Sign up for a free account.

Similar topics

38
by: Aaron W. LaFramboise | last post by:
Hello, I understand that an easy way to make the standard std::priority_queue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the...
6
by: Der Andere | last post by:
Are priority queues implemented in the STL in Visual Studio 6? If no, which is the easiest way to simulate them? Multisets? BTW: The container contains pointers to instances of a class. The...
2
by: Kay | last post by:
A linked list is storing several names. I want to make a queue if I input a name that is same as the linked list. How to make each node of a linked list storing a queue that are different with each...
3
by: AMRaymo | last post by:
Can someone guide me in the right direction on how to enqueue and dequeue/pop and push within a linked list? I've figured out the basic idea, but getting the other options in it seems ot be a...
5
by: Dan H. | last post by:
Hello, I have implemented a C# priority queue using an ArrayList. The objects being inserted into the priority queue are being sorted by 2 fields, Time (ulong) and Priority (0-100). When I...
7
by: Michael D. Ober | last post by:
When calling Enqueue, the internal array may need to be reallocated. My question is by how much? In the old MFC array classes, you could tell MFC how many additional elements to add to the array...
3
by: Chris Lasher | last post by:
Hello, I am working with large graphs (~150,000 to 500,000 nodes) which I need decompose node-by-node, in order of a node's value. A node's value is determined by the sum of its edge weights....
1
by: yaarnick | last post by:
Create a linked list data structure library to hold strings. Then library should support the following linked list operations. Create() – Creates the linked list Insert() – Insert a string into the...
4
by: jjh5030 | last post by:
This is a programming assignment. You are asked to work with pointers. Be aware that error messages are often not very helpful when your pointers point to bad locations. Therefore, reserve...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.