#!/usr/bin/env python

import random
import copy
from collections import defaultdict
import heapq

def partition_bk(l,r, arr, pidx):
    start = l
    end = r-1
    pidx_val = arr[pidx]
    if (l>=r): return r

    #print("----> l = {}, r = {}, start = {}, end = {}".format(l,r,start, end))
    arr[pidx], arr[r] = arr[r], arr[pidx]
    while True:
        while (arr[start] <= pidx_val):
            start += 1
            if (start > end): break

        while (arr[end] > pidx_val):
            end -= 1
            if (start > end): break

        if (start > end): break
        arr[start], arr[end] = arr[end], arr[start]
        if start<end:
            start += 1
    #print("r = ", r, " start = ", start, ", end = ", end )
    arr[r], arr[start] = arr[start], arr[r]
    return start

def partition(l,r, arr, pidx):
    start = l
    pidx_val = arr[pidx]

    arr[pidx], arr[r] = arr[r], arr[pidx]
    for i in range(l,r):
        if (arr[i] <= pidx_val):
            arr[i], arr[start] = arr[start], arr[i]
            start+=1
    arr[r], arr[start] = arr[start], arr[r]
    return start

def find_kth_largest(k, arr):
    l = 0
    r = len(arr) - 1
    #print("looking for k ",k, " in ", arr)
    first = True
    while  l <= r:
        if first:
            pidx = 4
            first = False
        else:
            pidx = random.randint(l,r)
        #print("new pidx {}".format(pidx))
        pidx = partition(l, r, arr, pidx)
        #print("\nreturned pidx = ", pidx)
        #print(arr)
        #print()
        if pidx == k-1:
            return arr[pidx]
        elif pidx > k-1:
            r = pidx-1
            l = 0
        else:
            l = pidx+1
            r = len(arr)-1
        #print("new l = {l} , r = {r}".format(l=l, r=r))
    return -1

def find_kth_largest_sort(k,arr):
    return sorted(arr)[k-1]

def find_kth_largest_heap(k,arr):
   heapq.heapify(arr)
   for i in range(k-1):
       heapq.heappop(arr)
   return arr[0]


def test_kth_largest_parition():
    n = 1000
    for i in range(n):
        size = random.randint(10,500)
        k = random.randint(1,size)
        print("size = {}, k = {}".format(size,k))
        a = [ random.randint(1,50) for i in range(size)]
    #a = [24, 27, 15, 27, 3, 17, 14, 28, 3, 4]
        b = sorted(a)
        expected = b[k-1]
        print(a)
        print(b)
        print("expected={e}".format(e=expected))
        result = find_kth_largest_heap(k,a)
        print("result={r}".format(r=result))
        if (result != expected):
            print("error result is not ", expected)
            print(a)
            return

    print("solution is correct.")






#result = bst.find_largest_smaller_key(17)

#print("Largest smaller number is %d " % (result))

test_kth_largest_parition()