| 13 | // Custom heap operations |
| 14 | template <typename Iterator, typename Compare> |
| 15 | void sift_down(Iterator first, Iterator last, Iterator start, Compare comp) { |
| 16 | auto root = start; |
| 17 | auto child = first + 2 * (root - first) + 1; |
| 18 | |
| 19 | while (child < last) { |
| 20 | if (child + 1 < last && comp(*child, *(child + 1))) { |
| 21 | ++child; |
| 22 | } |
| 23 | |
| 24 | if (comp(*root, *child)) { |
| 25 | auto tmp = *root; |
| 26 | *root = *child; |
| 27 | *child = tmp; |
| 28 | |
| 29 | root = child; |
| 30 | child = first + 2 * (root - first) + 1; |
| 31 | } else { |
| 32 | break; |
| 33 | } |
| 34 | } |
| 35 | } |
| 36 | |
| 37 | template <typename Iterator, typename Compare> |
| 38 | void push_heap(Iterator first, Iterator last, Compare comp) { |