fork download
copy 
  1. /*
  2.     Copyright 2016 Marek "p2004a" Rusinowski
  3.     Binary Heap
  4. */
  5. #include <cstdio>
  6. #include <vector>
  7. #include <functional>
  8. #include <algorithm>
  9. #include <random>
  10.  
  11. using namespace std;
  12.  
  13. template<class T, class Compare=less<T>>
  14. class BinHeap {
  15.     Compare comp;
  16.     vector<T> a;
  17.  
  18.     size_t left_child(size_t i) { return 2 * i + 1; }
  19.     size_t right_child(size_t i) { return 2 * i + 2; }
  20.     size_t parent(size_t i) { return (i - 1) / 2; }
  21.  
  22.     void heapify(size_t i) {
  23.         size_t highest = i;
  24.         if (left_child(i) < a.size() && comp(a[left_child(i)], a[highest])) {
  25.             highest = left_child(i);
  26.         }       
  27.         if (right_child(i) < a.size() && comp(a[right_child(i)], a[highest])) {
  28.             highest = right_child(i);
  29.         }
  30.         if (highest != i) {
  31.             swap(a[i], a[highest]);
  32.             heapify(highest);
  33.         }
  34.     }
  35.  
  36.   public:
  37.     explicit BinHeap(const Compare& comp_ = Compare()) : comp(comp_) {}
  38.  
  39.     template<class InputIt>
  40.     BinHeap(InputIt first, InputIt last, const Compare& comp_ = Compare()) : comp(comp_), a(first, last) {
  41.         for (size_t i = a.size() / 2; i > 0; --i) {
  42.             heapify(i);
  43.         }
  44.         heapify(0);
  45.     }
  46.  
  47.     const T& top() const {
  48.         return a[0];
  49.     }
  50.  
  51.     T pop() {
  52.         T elem = move(a[0]);
  53.         a[0] = move(a.back());
  54.         a.pop_back();
  55.         heapify(0);
  56.         return elem;
  57.     }
  58.  
  59.     void insert(T&& value) {
  60.         a.emplace_back(move(value));
  61.         for (size_t i = a.size() - 1; i > 0 && comp(a[i], a[parent(i)]); i = parent(i)) {
  62.             swap(a[i], a[parent(i)]);
  63.         }
  64.     }
  65.  
  66.     size_t size() const {
  67.         return a.size();
  68.     }
  69.  
  70.     bool empty() const {
  71.         return a.empty();
  72.     }
  73. };
  74.  
  75. struct NonCopyable {
  76.     int value;
  77.     NonCopyable(int value_ = 0) : value(value_) {}
  78.     NonCopyable(const NonCopyable&) = delete;
  79.     NonCopyable& operator = (const NonCopyable&) = delete;
  80.  
  81.     NonCopyable(NonCopyable&&) = default;
  82.     NonCopyable& operator = (NonCopyable&&) = default;
  83. };
  84.  
  85. bool operator<(const NonCopyable& lhs, const NonCopyable& rhs) {
  86.     return lhs.value < rhs.value;
  87. }
  88.  
  89. int main() {
  90.     random_device rd;
  91.     default_random_engine gen(rd());
  92.     uniform_int_distribution<> dis(0, 100);
  93.  
  94.     vector<int> init;
  95.     for (int i = 0; i < 30; ++i) {
  96.         init.emplace_back(dis(gen));
  97.     }
  98.     BinHeap<int, greater<int>> heap1(init.begin(), init.end());
  99.     while (!heap1.empty()) {
  100.         printf("%d ", heap1.pop());
  101.     }
  102.     printf("\n");
  103.  
  104.     BinHeap<NonCopyable> heap2;
  105.     for (int i = 0; i < 30; ++i) {
  106.         heap2.insert(NonCopyable(dis(gen)));
  107.     }
  108.     while (!heap2.empty()) {
  109.         printf("%d ", heap2.pop().value);
  110.     }
  111.     printf("\n");
  112.     return 0;
  113. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
99 99 98 96 95 95 94 93 93 89 86 84 83 77 73 65 65 56 55 51 46 43 38 30 22 16 14 9 7 3 
7 9 11 11 19 26 26 30 40 48 48 52 53 57 62 65 67 71 72 73 80 82 88 88 90 91 93 94 100 100
https://ideone.com/omqUBP
Binary Heap
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!