• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

priority queue based on unsorted list(Java's LinkedList Class)

 
Ranch Hand
Posts: 85
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello all, I am having a really hard time thinking my way through implementing a priority queue using Java's LinkedList class. I understand the priority queue in general terms. Basically you insert key-value pairs into the PQ in any order; but remove entries(key-value pairs) based on highest priority- in my case lowest key. That is a simple concept but implementing it, seems hard to do, especially when I need to print out both the key and values pertaining to each entry. Ok, I have tackled this many different ways, and thus far the closest I have come to solving it was running off the array(array out bounds), however I then realized I need to use "generics" so I started over. Furthermore, I know I will have to have a entry class(innerclass in my PQList), however, is it essentially that I create a node class as well so that I can properly traverse though the list? I was thinking of storing each entry in a node( or could I treat an entry as a node?). Or could I use the listIterator to accomplish this? Any suggestions greatly appreciated. I have been through the text many times over and over again, but I find this ds text is too hard to follow(data structures & algorithms 4th edition Authors: Mihcael Goodrich & Roberto Tamassia.) I always thought textbooks are to reinforce your understanding; not confuse you more. jk
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
First of all, don't implement a priority queue using a LinkedList -- it's not a good choice at all. The priority queue algorithm depends on being able to access list items by index, which is a slow operation on a LinkedList. If you have to use a List, use an ArrayList; but really, using a plain array would be just fine.

You've confused yourself terribly with the terms "entry class" and "node class". There's a list, and it contains items -- let's call them "entries". That's it.

Does your data structures text talk about the concept of a "binary heap"? To implement a priority queue, what you have to have are two methods: one to add an item to the bottom of the list and then "fix up" the list -- swap items with the new items until the whole list is once again a well-formed binary heap.

The other method removes the first item in the list and then "fixes down" -- pushes the "hole" down the heap by swapping items into it until once again you have a well-formed heap.

That's all you need to do. Concentrate on the fixup (heap-building) method first.
 
Mike Smith
Ranch Hand
Posts: 85
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Ernest,
yes I have learned about heaps, however, the instructor wants it done with a List from the Java api. It is suppose to be an easy problem, however, I find myself puzzled. I will try the ArrayList, even though he told me to use the LinkedList(maybe he made a mistake). He did make it sound like it should be fairly similar to the stack(which I used the ArrayList to implement). Thanks again for helping out. It is greatly appreciated.
 
Ernest Friedman-Hill
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Note that there is a PriorityQueue class in JDK 1.5. It's not actually implemented using a Java List, but it does use an array -- i.e., it's much closer to ArrayList than LinkedList.
 
Mike Smith
Ranch Hand
Posts: 85
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ok, I don't know if I am better off now, but my program doesn't give me array out of bounds error anymore; except now it doesn't return the minimum key. I have double checked and yes I need to use the LinkedList. 0(1) insertions are the only must. Here is my code maybe some one can see something that I am not seeing.




Once again, any suggestions are greatly appreciated. I have been working on this for what seems like forever; it must be something simple.
cheers
 
Ernest Friedman-Hill
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My goodness, if that's all that matters, then why use a heap at all? Just add each new item to the end of the LinkedList, which is O(1) for the Java implementation. For the poll() operation (i.e., to retrieve the lowest item) just search the whole list, which is O(N).
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
To be fair, it looks to be like that's what Mike is attempting to do - more or less. There's nothing in the code resembling a balanced binary heap. He's adding new elements to the beginning of the list rather than the end, but for a LinkedList either is equally easy.

The method min() looks potentially useful, but it's not called from any code shown.

Looking at the variables head, min, temp, i, num: one of these is completely unused, and three of them are used in one method only - those three could be local variables instead. In general it's a good idea to limit the scope of all variables as much as possible - don't expose a variable to more than one method if you don't need to. It just creates opportunities for confusion. Unused variables (and unused code in general) should be deleted entirely, as it just clutters things up.

But that's nothing compared to:

Look at where this is declared - it's an instance variable. You're attempting to use the same Iterator throughout the lifetime of the class. This is unacceptable - you will get a ConcurrentModificationException the moment you actually call the min method more than once. An Iterator should be used exactly once, no more. So the preferred way to use it would be to call iterator() at the beginning of a loop, NOT as part of the initialization of an instance field which would be reused. Every time you start a new loop, you need a new iterator.
 
Mike Smith
Ranch Hand
Posts: 85
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi guys, thanks for the input. I have taken your suggestions into account, along with recoding portions of my code; but now I get the following errors

Size Before:4
Is the priority queue empty? false
Exception in thread "main" java.lang.NullPointerException
at PqList.min(PqList.java:56)
at PqList.removeMin(PqList.java:76)
at PqListTest.main(PqListTest.java:16)

My modified code is


test class



I know there is definitely something wrong with my min() function. If all goes well it should return the entry with the minimum key. Furthermore, my removeMin() function should be able to call the min() function assign the minimum entry to another entry; then delete it from my list. However, It is crashing. I really don't understand how to fix this. The linked list should be dynamic ds so the first value added to the list could have a key of 1000 and the list should be able to accomadate it, correct me if I am wrong. Once again any suggestions greatly appreciated.
cheers
mike
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, that's a fairly standard NullPointerException. Look at the first line of the stack trace:

So, take a look at line 56 of PqList.java. What's on that line that could possibly be null? How can you change the code so it's not null?
 
Ernest Friedman-Hill
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And I'll also remind you that Jim said something about the ListIterator not being a member variable, but a local variable. The way you use any kind of Iterator is to create a new object right when you want to do some iterating -- i.e., a "while (it.hasNext())" is almost invariably immediately preceded by some variation on "Iterator it = something.iterator()".
 
Mike Smith
Ranch Hand
Posts: 85
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks guys for all the help. I managed to fix it. It works! Thanks again.
cheers
Mike
 
reply
    Bookmark Topic Watch Topic
  • New Topic