Heaps

[azzamqazi]

Hi guys,
I have a quesiton if someone can help me out here i will great
appreciate it. I am trying to use heaps for implementation of Priority
Queues. I wanna know what should i import in order for the Heaps to
work?? Thank you so much guys

 

[Roedy Green]

I have a quesiton if someone can help me out here i will great
appreciate it. I am trying to use heaps for implementation of Priority
Queues. I wanna know what should i import in order for the Heaps to
work?? Thank you so much guys

"Heap" in Java, usually refers to where newly allocated objects live.
You seem to be using it as the name of some specific class. What is
its full package name? and where can you read up on it?

 

[Eike Preuss]

Hi guys,
I have a quesiton if someone can help me out here i will great
appreciate it. I am trying to use heaps for implementation of Priority
Queues. I wanna know what should i import in order for the Heaps to
work?? Thank you so much guys

Heap == sorted binary tree?
Look at java.util.TreeMap

++ Eike

 

[Stefan Schulz]

"Heap" in Java, usually refers to where newly allocated objects live.
You seem to be using it as the name of some specific class. What is
its full package name? and where can you read up on it?

He means the sorted heap data structure covered in most introductory
lectures on algorithms and data structures. It does not offer a very
strict ordering, but allows very fast findMin() (in fact, constant time),
while retaining logarithmic insert()

 

[Stefan Schulz]

Hi guys,
I have a quesiton if someone can help me out here i will great
appreciate it. I am trying to use heaps for implementation of Priority
Queues. I wanna know what should i import in order for the Heaps to
work?? Thank you so much guys

There is a Priority Queue implementation in java, java.util.PriorityQueue.
If you just need a PQ, it offers all the features of a heap (and i am
almost willing to bet is implemented as a heap). However, if this is your
homework, you will need to work yourself.

Or just read and understand the source code. Which is sometimes harder
then doing it yourself, so i really suggest you do it yourself. After all,
usually the lectures will cover the most common way to implement it
(array-based).

 

[Thomas Weidenfeller]

Heap == sorted binary tree?

If we talk about the heap data structure, you missed an importand part
in your description, the representation as an array.

Look at java.util.TreeMap

That's a red-black tree.

But I guess the OP is actually looking at java.util.PriorityQueue. Its
API documentation talks about some "priority heap". Which is just a hint
about its internal implementation.

In case the OP talks about java.util.PriorityQueue, then there is no
need to deal with the heap directly. Just stuffing elements into the
Queue and fetching them, and probably providing an explicit Comparator
should be enough. One doesn't get directly exposed to the
PriorityQueue's heap, and one shouldn't need to.

/Thomas

 

[Roedy Green]

He means the sorted heap data structure covered in most introductory
lectures on algorithms and data structures. It does not offer a very
strict ordering, but allows very fast findMin() (in fact, constant time),
while retaining logarithmic insert()

in other words , a HeapSort style heap. See
http://mindprod.com/jgloss/heapsort.html