In article <ae6c3191-1167-43eb-9d36-23c7c49b5...@l28g2000vba.googlegroups.com>, Douglas Alan <darkwate...@gmail.com> wrote: > >I couldn't find a good algorithms forum on the Internet, so I guess >I'll ask this question here instead: Is it possible to efficiently >maintain a binary search tree in a flat array (i.e., without using >pointers), as is typically done for a binary heap? > >It *is* possible, of course, to keep an ordered list in a flat array, >and then do a binary search on the ordered array, but then insertion >and deletion are O(n), rather than O(log n).
Still, unless your list is large (more than thousands of elements), that's the way you should go. See the bisect module. Thing is, the speed difference between C and Python means the constant for insertion and deletion is very very small relative to bytecode speed. Keep in mind that Python's object/binding model means that you're shuffling pointers in the list rather than items. -- Aahz (a...@pythoncraft.com) <*> http://www.pythoncraft.com/ "If you think it's expensive to hire a professional to do the job, wait until you hire an amateur." --Red Adair -- http://mail.python.org/mailman/listinfo/python-list
