| 3084 | } |
| 3085 | |
| 3086 | function siftDown(heap, node, i) { |
| 3087 | var index = i; |
| 3088 | var length = heap.length; |
| 3089 | |
| 3090 | while (index < length) { |
| 3091 | var leftIndex = (index + 1) * 2 - 1; |
| 3092 | var left = heap[leftIndex]; |
| 3093 | var rightIndex = leftIndex + 1; |
| 3094 | var right = heap[rightIndex]; // If the left or right node is smaller, swap with the smaller of those. |
| 3095 | |
| 3096 | if (left !== undefined && compare(left, node) < 0) { |
| 3097 | if (right !== undefined && compare(right, left) < 0) { |
| 3098 | heap[index] = right; |
| 3099 | heap[rightIndex] = node; |
| 3100 | index = rightIndex; |
| 3101 | } else { |
| 3102 | heap[index] = left; |
| 3103 | heap[leftIndex] = node; |
| 3104 | index = leftIndex; |
| 3105 | } |
| 3106 | } else if (right !== undefined && compare(right, node) < 0) { |
| 3107 | heap[index] = right; |
| 3108 | heap[rightIndex] = node; |
| 3109 | index = rightIndex; |
| 3110 | } else { |
| 3111 | // Neither child is smaller. Exit. |
| 3112 | return; |
| 3113 | } |
| 3114 | } |
| 3115 | } |
| 3116 | |
| 3117 | function compare(a, b) { |
| 3118 | // Compare sort index first, then task id. |