# Kth Largest Element in a Stream — LeetCode 703

## Difficulty: Easy; Category: Heap

What is Heap?

Heap is a complete binary tree-based data structure. It can be divided into two types:

- Max-heap: the root node must be the greatest one, and all the parents are greater than their children.
- Min-heap: the root node must be the smallest one, and all the parents are smaller than their children.

And python has module *heapq *to implement the heap data structure:

*heapify(x)*: transfer a list type value into a heap data structure (min-heap)*heappush(heap, item)*: put the item into the heap*heappop(heap)*: pop out the smallest value from the heap*heappushpop(heap, item)*: put the item into the heap then pop out the smallest value.

The time complexity of* heapify() is O(N), heappush()* and heappop() art both O(log N). The pop operation is O(log N) because you need to modify the position of another element to maintain the heap.

*Note: When the question asks for the kth value, think about using Heap.*

Take **Example 1** as an example:

In order to get the 3rd largest item in the given list [4,5,8,2], we take the item from the largest to the 3rd one 8 -> 5 -> 4, making them into a considered list. And 2 will never be considered no matter what next item is added.

When an added item comes, determine is it bigger than the smallest number in the considered list or not, if yes, pop out the smallest one in the considered list and push the item into the list.

considered list = [4, 5, 8]

added item = 3

-> no change, return 4

considered list = [4, 5, 8]

added item = 5

-> pop 4, push 5, new considered list become [5, 5, 8], return the new 3rd largest item 5

and so on.

**Solution**

def __init__(self, k, nums):

"""

:type k: int

:type nums: List[int]

"""

self.k = k

# reverse the list and get largest to kth largest items

self.stream = sorted(nums, reverse=True)[:k]

heapify(self.stream)def add(self, val):

"""

:type val: int

:rtype: int

"""

# if not enough of item, directly push into stream

if len(self.stream) < self.k:

heappush(self.stream, val)

elif self.stream[0] <= val:

heappop(self.stream)

heappush(self.stream, val)

# return the first one in stream,

# which is the kth largest item

return self.stream[0]