1
\$\begingroup\$

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);
  }
}
\$\endgroup\$
2
\$\begingroup\$
  • Don't specify the array size in int arr[5] = {2, 1, 5, 4, 3};. int arr[] = {2, 1, 5, 4, 3}; will cause less maintenance issues.

  • Don't use magic numbers. All other occurrences of 5 should be replaced with either sizeof arr / sizeof *arr or much better turn arr into an std::array and use arr.size().

  • I don't like the combination of while (true) with a conditional break. Not sure how to get around it though.

  • I don't understand what the static_cast<unsigned> are for. Casts are not very appealing.

  • You use auto for basically everything including unsigned ints, but then you explicitly name the type typename std::iterator_traits<RandIt>::value_type when auto would suffice.

  • I would appreciate some comments. I don't actually know what SiftUp and SiftDown do and why they are not hidden in some heap implementation. I suppose returning when n < 2 is because you are heapifying the array and an array of less than 2 elements it automatically a heap, but I'm not sure.

  • The code in main is essentially a demo how to use the code. That is good. You could flesh that out a bit though. I made a move only type to check if you screwed up move semantics somewhere. You probably did too. Leave the check in. Also add an assert to make sure the resulting array is 5 4 3 2 1. (that is the correct result, right?). Therefore, when people mess with optimize the code they will be notified when they screw up. Add a case with an empty array, 1 element array and an array with a bunch of equal elements to show you thought about edge cases.

  • SiftUp and SiftDown could probably use some asserts to check if invariants hold. This also documents that there are invariants and what they are and you are told when you break them.

  • I would add some line breaks and even parenthesis to if statements. That is a style/habit thing through. If you can get your hands on code written by the interviewer's company try to mimic their style.

  • last in SiftDown should be a const & to avoid an unnecessary copy. Same goes or first in SiftDown, but then you need to pass std::begin(arr) instead of just arr.

After having criticized a lot let me say this: I would probably hire you. You show a good understanding of C++ and should be easy to shape into a good software developer. Good luck!

\$\endgroup\$
  • \$\begingroup\$ Thanks for the detailed and nice review. 1) I explicitly specified the array extent mainly because I don't want the reader to count the size himself. I will use std::vector instead. std::array cannot have the extent deduced from the initializer. 2) Signed-unsigned conversion can be potentially dangerous. So I made it explicit with static_cast. 3) The value_type thing is really my fault. Nice catch! 4) You get it right. A single element is a heap trivially. \$\endgroup\$ – Lingxi Feb 5 '16 at 10:47
  • \$\begingroup\$ 5) I agree with your suggestion about unit testing. But I'm afraid I cannot push it very far, given the limited time for an interview session. 6) I omitted assert and some braces, mainly because I want to keep the code compact so I can review it quickly myself for possible issues during an interview. By the way, I get your point and agree with it :-) 7) Since iterators are copied in the standard library. I followed it. Note that, in practice, copy will most probably not happen. Copy elision will kick in. Thanks for the review again and the nice words. It does help :-) \$\endgroup\$ – Lingxi Feb 5 '16 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.