commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
Subject Re: [collections] BinaryHeap and PriorityQueue
Date Fri, 02 Jan 2004 13:11:29 GMT
>  from:    Phil Steitz <>
> > I was also looking at the heap impl and wondering if the compare method
> > could check for ascendingOrder, then removing the need for near duplicate
> > methods (one for minHeap, one for maxHeap) elsewhere. Would this be a good
> > change?
> That would simplify the code, but might cost something in overall 
> performance (since compare is "hot"). Could be that's why the original 
> author(s) set it up the way it is?  Should be trivial. Might be worth 
> playing with.
Its hassle vs absolute performance. Always tricky in collections.

> Another solution would be to just have the constructor reverse the 
> comparator for maxHeaps (using ComparatorUtils.reversedComparator). There 
> the cost would be stack operations for each compare (calling through to 
> the reversed comparator).
The comparator is returned by a method in PriorityBuffer, so this might cause problems. (Of
course the null comparator could similarly be represented by a ComparableComparator at the
cost of an object creation)

> Another (small?) consideration is backward compatability for anyone who 
> has subclassed BinaryHeap (assuming we are not going to deprecate), since 
> all of the percolateXxx methods are protected, not private.
No backwards compatability issues - BinaryHeap is final, PriorityBuffer is new :-)


To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message