Heap Trick

I learned a neat trick regarding heaps today. Here's how it goes:

• Take the number of nodes in the heap and write that number down in binary.
• Erase the most significant bit.
• Starting at the root, go to the left child when you see a zero, and go to the right child when you see a one.
• When you run out of binary digits, you will be at the last node.

So if you don't feel like storing a pointer to the last node in a heap, you can use this little trick instead. Try it, it works!