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). It would also clearly be possible to store a balanced binary tree in a flat array, storing the children of the node at index i at indices 2*i and 2*i + 1, just as one does for a binary heap. But if you do that, I don't know if you could then do insertions and deletions in O(log n) time. One idea that came to mind, is that maybe it is possible using a "treap", which is a combination of a binary heap and a binary search tree. Insertions and deletions in binary heaps can be done in O(log n) in a flat array, but I don't know if this is also true for a treap, since you also have the binary search tree invariants to maintain, in addition to the binary heap invariants. For all I know, this might cause rotations to no longer be O(log n). |>ouglas -- http://mail.python.org/mailman/listinfo/python-list
