#include <algorithm>
#include <cassert>
#include <functional>

#include <iostream>
#include <iterator>

template< class RandomIt, class Compare >
constexpr void pop_mid_heap(RandomIt first, RandomIt last, RandomIt item_to_pop, Compare comp) {
    assert(std::is_heap(first, last)); //this is compiled out of release builds
    assert(first<=item_to_pop);
    assert(item_to_pop<last);
    using std::swap;
    std::size_t new_size = last - first - 1;
    if (new_size == 0) return;
    //swap the end of the range and item_to_pop, so that item_to_pop is at the end
    swap(*item_to_pop, *--last);
    if (new_size == 1) return;
    //If item_to_pop is bigger than it's parent, then swap with the parent
    bool moved_up = false;
    RandomIt swap_itr;
    while (true) {
        std::size_t offset = item_to_pop - first;
        if (offset == 0) break; //item_to_pop is at root: exit loop 
        swap_itr = first + offset / 2;
        if (comp(*item_to_pop, *swap_itr)) 
            break; //item_to_pop smaller than it's parent: exit loop
        swap(*item_to_pop, *swap_itr); //swap with parent and repeat
        item_to_pop = swap_itr;
        moved_up = true;        
    }
    if (moved_up) return; //if we moved the item up, then heap is complete: exit
    //If biggest child is bigger than item_to_pop, then swap with that child
    while (true) {
        std::size_t offset = item_to_pop - first;
        std::size_t swap_idx = offset * 2 + 1;
        if (swap_idx >= new_size) break; //no children: exit loop
        swap_itr = first + swap_idx;
        if (swap_idx+1 < new_size && comp(*swap_itr, *(swap_itr+1))) //if right child exists and is bigger, swap that instead
            ++swap_itr;
        if (!comp(item_to_pop, swap_itr)) break; //item_to_pop bigger than biggest child: exit loop
        swap(*item_to_pop, *swap_itr); //swap with bigger child and repeat
        item_to_pop = swap_itr;
    }
}
template< class RandomIt >
constexpr void pop_mid_heap(RandomIt first, RandomIt last, RandomIt item_to_pop) {
    pop_mid_heap(first, last, item_to_pop, std::less<>{});
}

#include <vector>

int main() {
    for(int i = 0; i < 15; i++ ) {
        std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
        std::make_heap(v.begin(), v.end());
        pop_mid_heap(v.begin(), v.end(), v.begin()+i);
        std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout,","));
        std::cout << ' ' << i << '\n';
    }
}