Binary heap construction and maintenance boil down to the two basic operations: sift up and sift down. Following are generic template implementations of the two operations. Any comments are welcome. I'm preparing for an interview, and I hope my code will appeal to the interviewer :-)
/// Compile with `-std=c++14`.
#include <cassert>
#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <iterator>
#include <utility>
template <class RandIt, class Less = std::less<void>>
void SiftDown(RandIt first, RandIt last, Less&& less = Less{}) {
auto n = static_cast<unsigned>(last - first);
if (n < 2) return;
auto child = 1u;
if (2 < n && less(first[1], first[2])) ++child;
if (less(first[0], first[child])) {
typename std::iterator_traits<RandIt>::value_type val =
std::move(first[0]);
first[0] = std::move(first[child]);
while (true) {
first += child;
n = static_cast<unsigned>(last - first);
if (n < 2) break;
child = 1u;
if (2 < n && less(first[1], first[2])) ++child;
if (! less(val, first[child])) break;
first[0] = std::move(first[child]);
}
first[0] = std::move(val);
}
}
template <class RandIt, class Less = std::less<void>>
void SiftUp(RandIt first, RandIt last, Less&& less = Less{}) {
auto n = static_cast<unsigned>(last - first);
if (n < 2) return;
auto parent = n / 2 - 1;
if (less(first[parent], last[-1])) {
typename std::iterator_traits<RandIt>::value_type val =
std::move(last[-1]);
last[-1] = std::move(first[parent]);
while (true) {
last = first + parent + 1;
n = static_cast<unsigned>(last - first);
if (n < 2) break;
parent = n / 2 - 1;
if (! less(first[parent], val)) break;
last[-1] = std::move(first[parent]);
}
last[-1] = std::move(val);
}
}
int main() {
int arr[5] = {2, 1, 5, 4, 3};
auto it = arr;
while (true) {
SiftUp(arr, it);
if (it == arr + 5) break;
++it;
}
for (auto i = 0; i < 5; ++i) {
std::cout << *arr << ' ';
std::iter_swap(arr, --it);
SiftDown(arr, it);
}
}
