The Use of a Fixed Height Binary Tree to Accelerate the Determination of the Medians of Subarrays

摘要

The new method for calculation the median of an array and their subarrays using a fixed-height binary tree is described. It is shown that such tree allows to find the element, determine the median of the array, or any of its ordinal statistics, by making no more comparisons than its double height. The computation time of calculation the medians of different types of arrays and continuous subarrays by the algorithms of both the traditional and the proposed methods is analyzed. It is shown that instead of the known sorting methods it is expedient to use Hoare partitioning to determine the medians of different arrays and unrelated subarrays. In order to identify the median sequence of continuous nested subarrays, the method of two pyramids could be used. And it is advisable to use a fixed-height binary tree to find the median of neighboring subarrays.