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()