Wednesday, October 3, 2007

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!

2 comments:

  1. Trad-off the time to lookup the last node in heap rather than storing a pointer there? Probably not worth it.

    But on a coolness rating (that's unintuitive to me at first glance) - 10/10 ;)

    ReplyDelete

Comments are moderated - please be patient while I approve yours.

Note: Only a member of this blog may post a comment.