java heapify method using priorityQueue

Question

I used priorityQueue as a max-heap implementation in my java program. Right now I need to heapify the created heap for calculating the maximum value. It seems that priorityQueue does not implement heapify method. So my question would be is there anyway for handling this problem using priorityQueue? If no, is there any reliable implementation for Max-heap in java that has heapify method? Note that my program use its own comparator. So this implementation should support that.

Some more explanation:

PriorityQueue<Customer> marginalGainHeap = new PriorityQueue<Customer>(
            1, new Comparator<Customer>() {
                public int compare(Customer c1, Customer c2) {
                    return Double.compare(c1.getMarginalGain(),
                            c2.getMarginalGain());
                }
            });

Suppose a marginalGain value changed for "node" object which is a type of "Customer". one solution would be

marginalGainHeap.remove(node)
marginalGainHeap.add(node)

but there is a problem:

It adds some extra latency to my program. I want to be as efficient as possible.

So if it is priority queue then you have max at the beginning (or at the end) of the queue ? — FazoM
– FazoM, Commented Feb 24, 2014 at 10:42
I am going to retrieve update some values in heap and retrieve the one with maximum value (root) — Ali
– Ali, Commented Feb 24, 2014 at 10:43
@Fazovsky Not necessarily, what if a child node updated and its value be more than root? — Ali
– Ali, Commented Feb 24, 2014 at 10:45
Your priority queue should maintain order of the elements on the update. i.e. if value changes then order might also need to change — FazoM
– FazoM, Commented Feb 24, 2014 at 10:45

peter.petrov · Accepted Answer · 2014-02-24 10:47:45Z

3

A priority queue is already a heap, so it does not need a heapify method.
This method is usually implemented on structures which are not heaps.

So just add/remove elements to/from your queue and just
assume you have the max elements at position 0 (at the root).

edited Feb 24, 2014 at 10:47

answered Feb 24, 2014 at 10:42

peter.petrov

39.6k23 gold badges114 silver badges193 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Ali Over a year ago

How can I remove that value? first I need to find that value so this process will add some latency at run-time. BTW, what method could handle this situation?

peter.petrov Over a year ago

Look at the methods poll and offer. docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

Peter Lawrey Over a year ago

@Alin You poll() a Queue to remove an element.

Serguei Fedorov Over a year ago

That's great, except when the priority of an item changes and it has to be resorted. As of right now, you have to remove and then add it back into the queue. This is much more expensive.

wilmol Over a year ago

@SergueiFedorov just checking, you need to remove and reinsert the specific item? Something like queue.add(queue.remove()); doesn't work?

Collectives™ on Stack Overflow

java heapify method using priorityQueue

1 Answer 1

5 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Related