Design a linear-time algorithm for the previous problem. 

Data From Previous Problem

Suppose we are given a sorted sequence S of items (x₀, x₁,...,x_n−1) such that each item xi in S is given a positive integer weight ai. Let A denote the total weight of all elements in S. Construct an O(n log n)-time algorithm that builds a search tree T for S such that the depth of each item ai is O(log A/a_i). 

Find the item x_j with largest j such that  Consider putting this item at the root and recursing on the two subsequences that this induces.

Transcribed Image Text:

j-1 i=0 0; くA/2 a; <