New answers tagged heaps
0
Suppose an array $A$ is a maxheap. Inserting a large element in the first position of $A$ does not necessarily preserve the maxheap property. The maxheap property requires a node's value to be larger than both its children's values, for each node in the tree. If the value inserted in the first position is larger than all values in the array, then the ...
0
Store the window in a balanced binary search tree. Each time a value arrives, add it to the tree, remove the one leaving the window, compute the median, and output it. Each of those operations can be done in $O(\log k)$ time, so the total running time to process $n$ items will be $O(n \log k)$.
0
My question is why use floor(length(a)/2)? How is it different than using length(a)? Is this the same thing?
Since every node at index $⌊𝑛/2⌋+1,⌊𝑛/2⌋+2,⋯,𝑛$ is a leaf node, it is also a root of a subtree max-heap. So no difference.
However, I want to point to another question, perhaps more interesting:
Why do we go backwards and don't start from 1 up ...
Top 50 recent answers are included
