| 2458 | } |
| 2459 | |
| 2460 | function siftDown(heap, node, i) { |
| 2461 | var index = i; |
| 2462 | var length = heap.length; |
| 2463 | var halfLength = length >>> 1; |
| 2464 | |
| 2465 | while (index < halfLength) { |
| 2466 | var leftIndex = (index + 1) * 2 - 1; |
| 2467 | var left = heap[leftIndex]; |
| 2468 | var rightIndex = leftIndex + 1; |
| 2469 | var right = heap[rightIndex]; // If the left or right node is smaller, swap with the smaller of those. |
| 2470 | |
| 2471 | if (compare(left, node) < 0) { |
| 2472 | if (rightIndex < length && compare(right, left) < 0) { |
| 2473 | heap[index] = right; |
| 2474 | heap[rightIndex] = node; |
| 2475 | index = rightIndex; |
| 2476 | } else { |
| 2477 | heap[index] = left; |
| 2478 | heap[leftIndex] = node; |
| 2479 | index = leftIndex; |
| 2480 | } |
| 2481 | } else if (rightIndex < length && compare(right, node) < 0) { |
| 2482 | heap[index] = right; |
| 2483 | heap[rightIndex] = node; |
| 2484 | index = rightIndex; |
| 2485 | } else { |
| 2486 | // Neither child is smaller. Exit. |
| 2487 | return; |
| 2488 | } |
| 2489 | } |
| 2490 | } |
| 2491 | |
| 2492 | function compare(a, b) { |
| 2493 | // Compare sort index first, then task id. |