0

Wikipedia says "increase key" is O(log n) for a binary heap, but it is referring to an internal function. I'm not asking about that: Imagine the data structure had an external/public function named modifyElement(currentElement, newElement).

enter image description here

Some constraints:

  1. The currentElement is in the data structure already, but it could be anywhere.
  2. newElement can be more valuable, less valuable, or equal value to the currentElement.

If this API existed on a heap, what would its Big O notation be (in runtime cost)?

I think it would be O(n + log n)1. A heap is partially sorted, not completely sorted. I think that means you would have to, worst-case, traverse every element to find the currentElement you're looking for, which would be O(n). Once you find it, you need to modify it and "re-heapify" it, which will cost O(log n).

Is O(n) the correct answer? If not, please explain. Thanks!

1: Simplified to O(n)

Improve this question
6
  • Language matters. You seem to be asking about the complexity of restructuring the tree, not the complexity of modifying an item. They may seem obviously connected to you but your search results are going to be massively influenced by what you search for. Commented Nov 21, 2023 at 2:21
  • 1
    Your reasoning seems correct for a binary heap. The decrease-key operation might be more efficient in other heap data structures, but wouldn't change overall O(n) for the search step. Of course it would be possible to have a data structure that is more efficient for this specific operation, e.g. by maintaining an index of positions in the heap. Using a fully sorted data structure like a b-tree, lots of operations become O(log n). Commented Nov 21, 2023 at 13:56
  • @Flater I'm not understanding what you are saying either, heh. I'm talking about both because you have to restructure after you modify. In addition, you have to search the tree to find the element you are trying to modify. Commented Nov 21, 2023 at 18:33
  • @amon ah a b-tree! Do you mean a binary search tree? So obvious in hindsight, that that would be a better structure for this API. Thanks. Commented Nov 21, 2023 at 18:38
  • 1
    @DanielKaplan A binary tree would also work, but a b-tree is a generalisation of a binary search tree that often performs better in practice. Instead of two childs, each node holds a sorted array of up to b children. Rebalancing is needed less often. B-trees are magical in that they're often faster in practice than small hash tables for keyed access, while maintaining sort order, and while being capable of scaling up massively (b trees or b+ trees are used in many file systems and databases for on-disk data, though no longer quite state of the art). Commented Nov 21, 2023 at 18:52

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.