Kth largest number in input stream

class MinHeap(object):
    def __init__(self,max_size):
        self.heap_list = [0]
        self.current_size = 0
        self.max_size = max_size

    def full(self):
        if self.current_size >=self.max_size:
            return True
        return False

    def perc_up(self,i):
        while i//2>0:
            if self.heap_list[i] < self.heap_list[i//2]:
                self.heap_list[i],self.heap_list[i//2] = self.heap_list[i//2],self.heap_list[i]
            i//=2
    def insert(self,value):
        if self.full() and self.peek()<value:
            self.del_min()
        self.heap_list.append(value)
        self.current_size+=1
        self.perc_up(self.current_size)

    def chid_id(self,i):
        if 2*i+1>self.current_size:
            return i*2
        else:
            if self.heap_list[2*i] <self.heap_list[2*i+1]:
                return 2*i
            else:
                return 2*i+1
    def  perc_down(self,i):
        while i*2 <=self.current_size:
            mc = self.chid_id(i)
            if self.heap_list[i] > self.heap_list[i*2]:
                self.heap_list[i],self.heap_list[i*2] = self.heap_list[i*2],self.heap_list[i]
            i = mc
    def peek(self):
        if self.heap_list:
            return self.heap_list[1]
        return None

    def del_min(self):
        max_val = self.heap_list[1]
        self.heap_list[1] = self.heap_list[-1]
        self.current_size -=1
        self.heap_list.pop()
        self.perc_down(1)  
        return max_val
def kthLargest(data,k):
    minheap = MinHeap(k)
    for val in data:
        minheap.insert(val)

    return minheap.peek()

results matching ""

    No results matching ""