Most developers never implement a hash map, a heap, or a binary search tree. They reach for std::unordered_map, std::priority_queue, std::map, and move on. That is correct for shipping code.
But it leaves a gap. When you have only ever used a heap, "k-th largest in O(n log k)" is a magic phrase. When you have built one, it is obvious: a size-k heap, push, pop when it overflows, done.
The trick is to build each structure exactly once, with tests checking every step, and then go back to using the standard library forever. The point is not to reinvent the wheel in production. The point is that after you have built the wheel, you can see it turning inside everyone else's code.
A short list worth doing by hand at least once:
- A dynamic array (grow, amortized push) so
O(1) amortizedstops being a phrase. - A hash map with collision handling so you trust the
O(1) average. - A binary heap so top-K and Dijkstra stop being mysterious.
- A binary search tree so "inorder is sorted" is something you have seen, not memorized.
Do it in a compiled language and let the compiler and a test harness be your reviewer. The friction is the lesson.
Build all of these by hand, in C++, with a compiler grading every step: https://iwtlp.com/track/dsa-cpp
Top comments (0)