private static PriorityQueue < Entry > initializeQueue ( double [ ] values , double [ ] weights , int nextIndex ) { checkArgument ( nextIndex > 0 , "nextIndex must be > 0" ) ; PriorityQueue < Entry > queue = new PriorityQueue <> ( nextIndex ) ; Entry right = new Entry ( nextIndex - 1 , values [ nextIndex - 1 ] , weights [ nextIndex - 1 ] , null ) ; queue . add ( right ) ; for ( int i = nextIndex - 2 ; i >= 0 ; i -- ) { Entry current = new Entry ( i , values [ i ] , weights [ i ] , right ) ; queue . add ( current ) ; right = current ; } return queue ; }
Create a priority queue with an entry for each bucket ordered by the penalty score with respect to the bucket to its right The inputs must be sorted by value in increasing order The last bucket has a penalty of infinity Entries are doubly - linked to keep track of the relative position of each bucket