CODEWITHSUNDEEP
python
user48571
user48571

Reputation: 27

Median of the medians of a list

I need a vector that stores the median values of the medians of the main list "v". I have tried something with the following code but I am only able to write some values in the correct way.

v=[1,2,3,4,5,6,7,8,9,10]
final=[]
nfac=0
for j in range (0,4):
    nfac=j+1
    for k in range (0,nfac):
        if k%2==0:
            final.append(v[10/2**(nfac)-1])
        else:
            final.append(v[9-10/2**(nfac)])

The first median in v=[1,2,3,4,5,6,7,8,9,10] is 5

Then I want the medians of the remaining sublists [1,2,3,4] and [6,7,8,9,10]. I.e. 2 and 8 respectively. And so on.

The list "final" must be in the following form:

final=[5,2,8,1,3,6,9,4,7,10]

Upvotes: 0

Views: 88

Answers (1)

dedObed
dedObed

Reputation: 1363

Please take a note that the task as you defined it is basically equivalent to constructing a binary heap from an array.

Definitely start by defining a helper function for finding the median: 

def split_by_median(l):
    median_ind = (len(l)-1) // 2
    median = l[median_ind]
    left = l[:median_ind]
    right = l[median_ind+1:] if len(l) > 1 else []
    return median, left, right

Following the example you give, you want to process the resulting sublists in a breadth-first manner, so we need a queue to remember the following tasks:

from collections import deque   
def construct_heap(v):
    lists_to_process = deque([sorted(v)])
    nodes = []
    while lists_to_process:
        head = lists_to_process.popleft()
        if len(head) == 0:
            continue

        median, left, right = split_by_median(head)
        nodes.append(median)
        lists_to_process.append(left)
        lists_to_process.append(right)

    return nodes

So calling the function finally:

print(construct_heap([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])) #  [5, 2, 8, 1, 3, 6, 9, 4, 7, 10]
print(construct_heap([5, 1, 2])) #  [2, 1, 5]
print(construct_heap([1, 0, 0.5, -1])) #  [0, -1, 0.5, 1] 
print(construct_heap([])) #  []

Upvotes: 1

Related Questions