| 878 | |
| 879 | template<class RandomAccessIterator, class Size, class Compare> |
| 880 | void correct_children(RandomAccessIterator first, |
| 881 | Size idx, Size count, Compare comp) |
| 882 | { |
| 883 | using aux::heap_left_child; |
| 884 | using aux::heap_right_child; |
| 885 | |
| 886 | auto left = heap_left_child(idx); |
| 887 | auto right = heap_right_child(idx); |
| 888 | |
| 889 | bool left_incorrect{comp(first[idx], first[left])}; |
| 890 | bool right_incorrect{comp(first[idx], first[right])}; |
| 891 | while ((left < count && left_incorrect) || |
| 892 | (right < count && right_incorrect)) |
| 893 | { |
| 894 | if (right >= count || (left_incorrect && comp(first[right], first[left]))) |
| 895 | { |
| 896 | swap(first[idx], first[left]); |
| 897 | |
| 898 | idx = left; |
| 899 | } |
| 900 | else if (right < count && right_incorrect) |
| 901 | { |
| 902 | swap(first[idx], first[right]); |
| 903 | |
| 904 | idx = right; |
| 905 | } // Else should not happen because of the while condition. |
| 906 | |
| 907 | left = heap_left_child(idx); |
| 908 | right = heap_right_child(idx); |
| 909 | |
| 910 | left_incorrect = comp(first[idx], first[left]); |
| 911 | right_incorrect = comp(first[idx], first[right]); |
| 912 | } |
| 913 | } |
| 914 | } |
| 915 | |
| 916 | /** |
no test coverage detected