[heap]99클럽 코테 스터디 10일차 TIL + 0789-kth-largest-element-in-a-stream

789. Kth Largest Element in a Stream

Easy

---

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

• KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
• int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

 

Example 1:

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

 

Constraints:

• 1 <= k <= 104
• 0 <= nums.length <= 104
• -104 <= nums[i] <= 104
• -104 <= val <= 104
• At most 104 calls will be made to add.
• It is guaranteed that there will be at least k elements in the array when you search for the kth element.

 

<내코드>

import heapq
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.heap = nums
        self.k = k
        heapq.heapify(self.heap)


    def add(self, val: int) -> int:
        if self.heap:
            heapq.heappush(self.heap, val)
            while self.k < len(self.heap):
                heapq.heappop(self.heap)
        else :
            self.heap.append(val)
            heapq.heapify(self.heap)
        heap_ = self.heap[0]

        return heap_


# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

# 실수1
# pop 은 없음

1. 어제와 비교

- 오늘은 최소힙이고, 어제는 최대힙이다.

그래서 기본적인 heapq에 구현된것을 그대로 이용이 가능했다.

그리고 최소힙을 이용하면 tree의 root 부분의 값을 쉽게 이용할 수 있음

 

- heapify 를 최초에 리스트를 넣어서 실제로 적용시켜봄

 

 

2. 헤맨 부분

(1) 왜 list.sort() 대신에 heapq를 이용해야하는가?

list.sort() 는 O(n log n) 이지만 heapq 는 O (log K) 로서 효율적임

왜냐하면 k 개만큼만 heap 을 살려두기 때문임

 

 

(2) nlargest() 사용의 문제

heapq.nlargest(self.k, self.heap)[-1]

이것을 사용하면 시간초과 문제가 발생됨

왜냐하면 만약에 k 값이 최초 주어진 크기(heap 의 크기)만큼 값이 인자로 들어오게 되면 사실상 복제와 마찬가지이기 때문임

 

 

 

<모범사례>

import heapq
from typing import List

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)  # Transform list into a heap, in-place, in linear time.
        # Keep only the k largest elements in the heap
        while len(self.heap) > k:
            heapq.heappop(self.heap)

    def add(self, val: int) -> int:
        # If the heap has less than k elements, add the new value
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        # If the new value is larger than the smallest element in the heap, replace it
        elif val > self.heap[0]:
            heapq.heapreplace(self.heap, val)
        # The root of the heap is the kth largest element
        return self.heap[0]

# Example usage:
kthLargest = KthLargest(3, [4, 5, 8, 2])
print(kthLargest.add(3))  # Output: 4
print(kthLargest.add(5))  # Output: 5
print(kthLargest.add(10)) # Output: 5
print(kthLargest.add(9))  # Output: 8
print(kthLargest.add(4))  # Output: 8

1. init 부분

- 여기서 k 만큼으로 heap 사이즈를 조정하는것을 미리 하는것이 수월함

 

2. add() 부분

크게 두가지 흐름임

1) k 보다 크기가 작을때 넣거나, 

2) 가장작은 root 의 값보다 새로 들어오는 값이 큰 경우 대체하거나

 

이렇게 하면 충분히 유지가 가능함

 

 

<보충학습>

1. heapq.heapreplace(self.heap, val)

heapreplace 는 pop 후 push 하는것이지만 더 효율적임

 

2. 최대힙, 최소힙의 사용사례차이

최대힙 : 힙 정렬, K번째 큰 수 찾기, 최대값 유지 등.

최소힙 : 우선순위 큐, K번째 작은 수 찾기, 스케줄링 문제 등.

 

3. 시간복잡도

pop / push : O(log n)

heapify : O(n)

으로 여기서 n은 트리의 높이임

 

여기서 만약 pop/ push 가 n 번하게 되면 O(n log n) 이 됨

 

4. 힙의 주요 용도

(1) 원하는 크기만큼 유지하기 (슬라이딩 윈도우)

슬라이딩 윈도우 : 전체 데이터 스트림이 아니라 특정 구간의 데이터 효율적 처리 위함

 

1) 실시간 모니터링 시스템 (최근 몇분 ~ 몇시간 동안) 의 최대 평균 추적

2) 데이터 스트림 최적화 (금융 최근 거래의 주가의 k 번째 추적)

3) 뉴스피드 (특정 기간 인기 뉴스)