fork(1) download
copy 
  1.  
  2. #include <algorithm>
  3. #include <cassert>
  4. #include <functional>
  5.  
  6. #include <iostream>
  7. #include <iterator>
  8.  
  9. template< class RandomIt, class Compare >
  10. constexpr void pop_mid_heap(RandomIt first, RandomIt last, RandomIt item_to_pop, Compare comp) {
  11.     assert(std::is_heap(first, last)); //this is compiled out of release builds
  12.     assert(first<=item_to_pop);
  13.     assert(item_to_pop<last);
  14.     using std::swap;
  15.     std::size_t new_size = last - first - 1;
  16.     if (new_size == 0) return;
  17.     //swap the end of the range and item_to_pop, so that item_to_pop is at the end
  18.     swap(*item_to_pop, *--last);
  19.     if (new_size == 1) return;
  20.     //If item_to_pop is bigger than it's parent, then swap with the parent
  21.     bool moved_up = false;
  22.     RandomIt swap_itr;
  23.     while (true) {
  24.         std::size_t offset = item_to_pop - first;
  25.         if (offset == 0) break; //item_to_pop is at root: exit loop 
  26.         swap_itr = first + offset / 2;
  27.         if (comp(*item_to_pop, *swap_itr)) 
  28.             break; //item_to_pop smaller than it's parent: exit loop
  29.         swap(*item_to_pop, *swap_itr); //swap with parent and repeat
  30.         item_to_pop = swap_itr;
  31.         moved_up = true;        
  32.     }
  33.     if (moved_up) return; //if we moved the item up, then heap is complete: exit
  34.     //If biggest child is bigger than item_to_pop, then swap with that child
  35.     while (true) {
  36.         std::size_t offset = item_to_pop - first;
  37.         std::size_t swap_idx = offset * 2 + 1;
  38.         if (swap_idx >= new_size) break; //no children: exit loop
  39.         swap_itr = first + swap_idx;
  40.         if (swap_idx+1 < new_size && comp(*swap_itr, *(swap_itr+1))) //if right child exists and is bigger, swap that instead
  41.             ++swap_itr;
  42.         if (!comp(item_to_pop, swap_itr)) break; //item_to_pop bigger than biggest child: exit loop
  43.         swap(*item_to_pop, *swap_itr); //swap with bigger child and repeat
  44.         item_to_pop = swap_itr;
  45.     }
  46. }
  47. template< class RandomIt >
  48. constexpr void pop_mid_heap(RandomIt first, RandomIt last, RandomIt item_to_pop) {
  49.     pop_mid_heap(first, last, item_to_pop, std::less<>{});
  50. }
  51.  
  52. #include <vector>
  53.  
  54. int main() {
  55.     for(int i = 0; i < 15; i++ ) {
  56.         std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
  57.         std::make_heap(v.begin(), v.end());
  58.         pop_mid_heap(v.begin(), v.end(), v.begin()+i);
  59.         std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout,","));
  60.         std::cout << ' ' << i << '\n';
  61.     }
  62. }
Success #stdin #stdout 0.01s 5456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
14,11,13,9,10,12,7,8,4,2,5,1,6,3,15, 0
15,10,14,9,5,13,7,8,4,2,1,12,6,3,11, 1
15,11,13,9,10,12,7,8,4,2,5,1,6,3,14, 2
15,11,14,8,10,13,7,1,4,2,5,12,6,3,9, 3
15,11,14,9,5,13,7,8,4,2,1,12,6,3,10, 4
15,11,14,9,10,12,7,8,4,2,5,1,6,3,13, 5
15,11,14,9,10,13,3,8,4,2,5,12,6,1,7, 6
15,11,14,9,10,13,7,1,4,2,5,12,6,3,8, 7
15,11,14,9,10,13,7,8,1,2,5,12,6,3,4, 8
15,11,14,9,10,13,7,8,4,1,5,12,6,3,2, 9
15,11,14,9,10,13,7,8,4,2,1,12,6,3,5, 10
15,11,14,9,10,13,7,8,4,2,5,1,6,3,12, 11
15,11,14,9,10,13,7,8,4,2,5,12,1,3,6, 12
15,11,14,9,10,13,7,8,4,2,5,12,6,1,3, 13
15,11,14,9,10,13,7,8,4,2,5,12,6,3,1, 14
https://ideone.com/7OboH5
language:
C++14 (clang 8.0)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!