@@ -47,20 +47,28 @@ module.exports = class PriorityQueue {
4747 const setPosition = this . #setPosition;
4848 const heap = this . #heap;
4949 const size = this . #size;
50+ const hsize = size >> 1 ;
5051 const item = heap [ pos ] ;
5152
52- while ( pos * 2 <= size ) {
53- let childIndex = pos * 2 + 1 ;
54- if ( childIndex > size || compare ( heap [ pos * 2 ] , heap [ childIndex ] ) < 0 )
55- childIndex = pos * 2 ;
56- const child = heap [ childIndex ] ;
57- if ( compare ( item , child ) <= 0 )
58- break ;
53+ while ( pos <= hsize ) {
54+ let child = pos << 1 ;
55+ const nextChild = child + 1 ;
56+ let childItem = heap [ child ] ;
57+
58+ if ( nextChild <= size && compare ( heap [ nextChild ] , childItem ) < 0 ) {
59+ child = nextChild ;
60+ childItem = heap [ nextChild ] ;
61+ }
62+
63+ if ( compare ( item , childItem ) <= 0 ) break ;
64+
5965 if ( setPosition !== undefined )
60- setPosition ( child , pos ) ;
61- heap [ pos ] = child ;
62- pos = childIndex ;
66+ setPosition ( childItem , pos ) ;
67+
68+ heap [ pos ] = childItem ;
69+ pos = child ;
6370 }
71+
6472 heap [ pos ] = item ;
6573 if ( setPosition !== undefined )
6674 setPosition ( item , pos ) ;
@@ -73,27 +81,30 @@ module.exports = class PriorityQueue {
7381 const item = heap [ pos ] ;
7482
7583 while ( pos > 1 ) {
76- const parent = heap [ pos / 2 | 0 ] ;
77- if ( compare ( parent , item ) <= 0 )
84+ const parent = pos >> 1 ;
85+ const parentItem = heap [ parent ] ;
86+ if ( compare ( parentItem , item ) <= 0 )
7887 break ;
79- heap [ pos ] = parent ;
88+ heap [ pos ] = parentItem ;
8089 if ( setPosition !== undefined )
81- setPosition ( parent , pos ) ;
82- pos = pos / 2 | 0 ;
90+ setPosition ( parentItem , pos ) ;
91+ pos = parent ;
8392 }
93+
8494 heap [ pos ] = item ;
8595 if ( setPosition !== undefined )
8696 setPosition ( item , pos ) ;
8797 }
8898
8999 removeAt ( pos ) {
90100 const heap = this . #heap;
91- const size = -- this . #size;
92- heap [ pos ] = heap [ size + 1 ] ;
93- heap [ size + 1 ] = undefined ;
101+ let size = this . #size;
102+ heap [ pos ] = heap [ size ] ;
103+ heap [ size ] = undefined ;
104+ size = -- this . #size;
94105
95106 if ( size > 0 && pos <= size ) {
96- if ( pos > 1 && this . #compare( heap [ pos / 2 | 0 ] , heap [ pos ] ) > 0 )
107+ if ( pos > 1 && this . #compare( heap [ pos >> 1 ] , heap [ pos ] ) > 0 )
97108 this . percolateUp ( pos ) ;
98109 else
99110 this . percolateDown ( pos ) ;
0 commit comments