| 2286 | } |
| 2287 | |
| 2288 | function siftDown(heap, node, i) { |
| 2289 | var index = i; |
| 2290 | var length = heap.length; |
| 2291 | |
| 2292 | while (index < length) { |
| 2293 | var leftIndex = (index + 1) * 2 - 1; |
| 2294 | var left = heap[leftIndex]; |
| 2295 | var rightIndex = leftIndex + 1; |
| 2296 | var right = heap[rightIndex]; // If the left or right node is smaller, swap with the smaller of those. |
| 2297 | |
| 2298 | if (left !== undefined && compare(left, node) < 0) { |
| 2299 | if (right !== undefined && compare(right, left) < 0) { |
| 2300 | heap[index] = right; |
| 2301 | heap[rightIndex] = node; |
| 2302 | index = rightIndex; |
| 2303 | } else { |
| 2304 | heap[index] = left; |
| 2305 | heap[leftIndex] = node; |
| 2306 | index = leftIndex; |
| 2307 | } |
| 2308 | } else if (right !== undefined && compare(right, node) < 0) { |
| 2309 | heap[index] = right; |
| 2310 | heap[rightIndex] = node; |
| 2311 | index = rightIndex; |
| 2312 | } else { |
| 2313 | // Neither child is smaller. Exit. |
| 2314 | return; |
| 2315 | } |
| 2316 | } |
| 2317 | } |
| 2318 | |
| 2319 | function compare(a, b) { |
| 2320 | // Compare sort index first, then task id. |