How does a PriorityQueue work ?
Jose Campana
Ranch Hand
Posts: 339
posted 8 years ago
Hello!
I've been having trouble learning how a PriorityQueue works..
Do you know if a PriorityQueue sorts elements when you add them ?
I'm asking because the behavior of this piece of code here is difficult to understand... (for me)
That code prints out:
Amazing : Fantastic
But If I change the line with the comment "//this line" for this line:
it prints out:
Fantastic : Outstanding
Which leads me into thinking that some sorting happens backstage.
Could somebody please tell me, How does a PriorityQueue work?
I'm assuming that If Sorting happens, the poll() method removes the last element in the PriorityQueue after sorting by natural order...
Am I correct?
please help me,
Jose
I've been having trouble learning how a PriorityQueue works..
Do you know if a PriorityQueue sorts elements when you add them ?
I'm asking because the behavior of this piece of code here is difficult to understand... (for me)
That code prints out:
Amazing : Fantastic
But If I change the line with the comment "//this line" for this line:
it prints out:
Fantastic : Outstanding
Which leads me into thinking that some sorting happens backstage.
Could somebody please tell me, How does a PriorityQueue work?
I'm assuming that If Sorting happens, the poll() method removes the last element in the PriorityQueue after sorting by natural order...
Am I correct?
please help me,
Jose
posted 8 years ago
Hi Jose,
A priority queue could work by sorting after each insertion, but it would be slow; each insertion would take time proportional to N*ln(N), where N is the size of the queue. But if you think about it, there's no reason for all the items in the queue to be sorted: you just need to know, at all times, which is the "first" item.
So instead, most priority queues use a data structure called a heap, which is a kind of partiallysorted binary tree. The tree is arranged so that every child node "below" a parent node in the tree would come after the parent if all the nodes were sorted; but the children of a parent aren't necessarily next if the tree were sorted. If you think about it, though, this means that the very first node in the sort is always at the root of the tree, and things are partially sorted as you move down the tree.
It turns out that after removing the root or adding a new child, you can restore the tree to a proper heap in ln(N) time, which is quite fast. This makes a heap an ideal data structure for implementing a priority queue.
A priority queue could work by sorting after each insertion, but it would be slow; each insertion would take time proportional to N*ln(N), where N is the size of the queue. But if you think about it, there's no reason for all the items in the queue to be sorted: you just need to know, at all times, which is the "first" item.
So instead, most priority queues use a data structure called a heap, which is a kind of partiallysorted binary tree. The tree is arranged so that every child node "below" a parent node in the tree would come after the parent if all the nodes were sorted; but the children of a parent aren't necessarily next if the tree were sorted. If you think about it, though, this means that the very first node in the sort is always at the root of the tree, and things are partially sorted as you move down the tree.
It turns out that after removing the root or adding a new child, you can restore the tree to a proper heap in ln(N) time, which is quite fast. This makes a heap an ideal data structure for implementing a priority queue.
Jose Campana
Ranch Hand
Posts: 339
posted 8 years ago
Hello again,
Complex, really complex I must say. So, Could I assume that there's No way I could know how objects are arranged inside my PriorityQueue ? with this I mean an Easy way...?
I'm really worried I don't wanna be stuck with a question like that on the SCJP exam.
Thank you for the insights Ernest!
They're always welcome.
Sincerely,
Jose
Complex, really complex I must say. So, Could I assume that there's No way I could know how objects are arranged inside my PriorityQueue ? with this I mean an Easy way...?
I'm really worried I don't wanna be stuck with a question like that on the SCJP exam.
Thank you for the insights Ernest!
They're always welcome.
Sincerely,
Jose
Jim Yingst
Wanderer
Sheriff
Sheriff
Posts: 18671
posted 8 years ago
You definitely don't need to understand how a PriorityQueue works internally for the SCJP exam. You might need to know that if you call toString() or if you iterate through the contents of the Queue, the order you get is not necessarily sorted by priority. Much like with a HashMap, if you iterate or call toString(), you can think of the results as being in random order. They're not really random, but the order is complicated and you don't really need to worry about it. Unless you're studying algorithms for, say, an algorithms class.
"I'm not back."  Bill Harding, Twister
Jose Campana
Ranch Hand
Posts: 339
posted 8 years ago
Howdi!
I'm grateful for your responses, It's so cool to know more about the details of the language, I'll have to leave the internal algorithms for later though.
And, I'm so relieved that questions about PriorityQueues in the SCJP exam, aren't as complicated as I imagined.
Have a nice day !
Keep up the fantastic work,
Jose
I'm grateful for your responses, It's so cool to know more about the details of the language, I'll have to leave the internal algorithms for later though.
And, I'm so relieved that questions about PriorityQueues in the SCJP exam, aren't as complicated as I imagined.
Have a nice day !
Keep up the fantastic work,
Jose
What are you doing? You are supposed to be reading this tiny ad!
the new thread boost feature brings a LOT of attention to your favorite threads
https://coderanch.com/t/674455/ThreadBoostfeature
