[Solved] Data structure and algorithm for Max/Min apple number search and update [closed]

by


You can impose a tree structure on an array. The leaves of the tree are the array itself. The next level up has one node for each pair of array elements. The next level up has four descendants for each node, and so on… 

       15

   13      14
 9   10  11  12
1 2  3 4 5 6 7 8

Here 1..8 might be the original data points, and the higher numbers show tree nodes that you can add. Now if you hold at each internal node the minimum and maximum value found amongst any of its descendants you will find the minimum and maximum value for the whole array at the root of the tree, and you can find the index involved by tracking down the tree to it, or by storing indexes as well as values. When you update a value at the leaves, you track up the tree, if necessary, to recalculate the minimum and maximum values stored at its parents. All of these actions take time O(log n) because that is the height of the tree.

As an example, suppose that the input data is 101..108. This will produce the following tree of maximum values, with the absolute maximum for the whole tree at the top:


                 108
       104                  108
  102        104       106       108
101  102  103  104  105  106  107  108

If you now change the value 104 to 109, you can see that you need only change the values up from here to the top of the tree to restore the invariants of the datastructure and get the new maximum at the top


                 109
       109                  108
  102        109       106       108
101  102  103  109  105  106  107  108

5

solved Data structure and algorithm for Max/Min apple number search and update [closed]