binary heap

heap.cc

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

bool default_predicate(int a, int b) { return a > b; }

struct Heap {
private:
  vector<int> data;
  bool (*predicate)(int, int);
  void build_heap(vector<int> &arr, int root);
  void heapify(vector<int> &arr, int root);

public:
  int top();
  void push(int x);
  int pop();
  bool empty();
  void print_stats();
  Heap() : predicate(default_predicate){};
  Heap(bool (*pred)(int, int)) : predicate(pred) {}
  Heap(vector<int> x, bool (*pred)(int, int)) : data(x), predicate(pred) {
    build_heap(data, 0);
  }
  Heap(vector<int> x) : data(x), predicate(default_predicate) {
    build_heap(data, 0);
  }
};

void Heap::heapify(vector<int> &arr, int root) {
  int newRoot = root;
  const int left = 2 * root + 1;
  const int right = 2 * root + 2;
  if (left < arr.size() && predicate(arr[left], arr[newRoot])) {
    newRoot = left;
  }
  if (right < arr.size() && predicate(arr[right], arr[newRoot])) {
    newRoot = right;
  }
  if (newRoot != root) {
    swap(arr[root], arr[newRoot]);
    heapify(arr, newRoot);
  }
}

void Heap::build_heap(vector<int> &arr, int root) {
  const int start = arr.size() / 2 - 1;
  for (int i = start; i >= 0; i--) {
    heapify(arr, i);
  }
}

// insert at the end and heapify from the bottom
void Heap::push(int x) {
  data.push_back(x);
  int index = data.size() - 1;
  index = index / 2 - (index % 2 == 0);
  while (index >= 0) {
    heapify(data, index);
    index = index / 2 - (index % 2 == 0);
  }
}

// replaced last node to first nodes and heapify from the top
int Heap::pop() {
  const int head = data[0];
  data[0] = *data.rbegin();
  data.pop_back();
  heapify(data, 0);
  return head;
}

int Heap::top() {
  if (empty())
    throw "NullPointerException";
  return data[0];
}

bool Heap::empty() { return data.empty(); }

void Heap::print_stats() {
  for (auto i : data) {
    cout << i << " ";
  }
  cout << endl;
}

int main() {
  Heap h([](int a, int b) -> bool { return a < b; });
  h.push(10);
  h.push(5);
  h.push(3);
  h.push(2);
  h.push(4);
  h.print_stats();
  h.push(15);
  h.print_stats();

  h = Heap({1, 3, 6, 5, 9, 8});
  h.print_stats();
}