6 ms·
I'm confused. I can follow the logic for O(sqrt n) searching. yeah, that's cool. But how to maintain the structure when inserting or deleting? Insertion for ex
by abcdabcd987 11y ago
I'm confused. I can follow the logic for O(sqrt n) searching. yeah, that's cool. But how to maintain the structure when inserting or deleting?
Insertion for example, if I want to insert a value which is smaller than the smallest element in the last heap, then it'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?
Or maybe I just have not caught the author's idea yet. :-(
BTW, why not BST, for everything is O(log n)?
Update: @nikic solved my questions. Thanks!
- wpears 11y agoBST is O(n) in the worst case (when a tree is completely unbalanced and is essentially a linked list)
- abcdabcd987 11y agoWell, it's not a big problem. This case won't exist in most BSTs. Even if it appears in some BST, splay tree for example, it will be amortized.
- skj 11y agoI'm not really sure what amortization you're talking about here. BSTs are O(n) lookup, and the pathological case is quite easy to achieve: add elements to it in sorted order. There are other trees that have O(lg n) lookup. Red-black trees are the canonical example.
- cporios 11y agoBSTs can have O(lg n) lookups. A Red-black tree is such an example. It is a self-balancing BST, so a red-black tree is a BST itself.
- hvidgaard 11y agoAnd BSTs can have O(n) lookup. The only property of a BST is that you know something about the value of the children compared to the parent. This means that a sorted linked list is a BST.
- Veedrac 11y agoSure, but abcdabcd987 was evidently not suggesting using a completely general BST. That there exists a BST with the mentioned properties is sufficient to validate the claim made; that there exists a BST which does not is irrelevant.
- skj 11y agoI believe your and abcdabcd987's use of the term BST is not exactly what is commonly used. A BST refers to both the data structure and the algorithm used to manage it. An RB tree is a different concept. An RB tree is a binary tree, certainly, since the term "binary tree" implies no algorithms, but it is not a "binary search tree" in its specific denotation.
- Veedrac 11y agohttps://en.wikipedia.org/wiki/Binary_search_tree#Types https://en.wikipedia.org/wiki/Binary_search_tree#Types > There are many types of binary search trees. AVL trees and red-black trees are both forms of self-balancing binary search trees.
- hvidgaard 11y agoTerminology is important. A BST is what I defined. A balanced BST has an extra property, but you don't get to call a balanced BST just a BST, it only adds to confusion and unclear communication.
- Veedrac 11y agoI don't agree with your use of terminology; to me "BST" is just as much a class of things as "mammal" is. I will agree though that it has added confusion.
- deciplex 11y agoI 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.