I&#x27;m confused. I can follow the logic for O(sqrt n) searching. yeah, that&#x27;s cool. But how to maintain the structure when inserting or deleting?<p>Insertion for example, if I want to insert a value which is smaller than the smallest element in the last heap, then it&#x27;ll have to be inserted into some heap in the middle, right? And since the heap is in the middle, say heap K, its size already reaches its upper limitation K^2. Then where should the new value go? If I insist on pushing it into heap K, then the heap will violate the size limitation. Should I split the oversized heap into several heaps some time? If it does split, will the O(sqrt n) searching time still holds?<p>Or maybe I just have not caught the author&#x27;s idea yet. :-(<p>BTW, why not BST, for everything is O(log n)?<p>Update: @nikic solved my questions. Thanks!