Re:An interesting data structure with search time O(sqrt n)
by deciplex on Monday November 30, 2015 @08:44PM
(#10653175)
I think for insertion, once you find the heap the new element should be inserted into, you would remove the max element from the heap, and re-heapify that subarray with the new element. Then you would insert the max you just removed into the next heap in the same way, and so on. That sounds like it could be less expensive than shifting the whole array, but I haven't done the math (and it seems that Alexandrescu hasn't either, yet).
Note that I'm making a couple assumptions about the data structure that were left unstated in the original post:
* Each element of each heap is less than every element of every subsequent heap.
* "When the max value in a heap is less than the searched element" was a typo and "When the max value in a heap is greater than the searched element" was intended.
Maybe I just totally misunderstand this data structure though :-( It's still morning for me.
Note that I'm making a couple assumptions about the data structure that were left unstated in the original post:
* Each element of each heap is less than every element of every subsequent heap.
* "When the max value in a heap is less than the searched element" was a typo and "When the max value in a heap is greater than the searched element" was intended.
Maybe I just totally misunderstand this data structure though :-( It's still morning for me.