hyunkookim 님의 블로그

215. Kth Largest Element in an Array class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # minheap 으로 만들고, k개 까지. 힙 개수 유지하게 하면, # k 개 보다 많으면 작은 것들 제거 # 그렇게 하면, minheap[0]에는 k번째 큰 것이 남아있음 heapq.heapify(nums) while( len(nums) > k): heapq.heappop(nums) return nums[0] 메모리 절약을 위해, k 개 만큼 우선 넣어서, minheap 만들고.1개씩 추가해서, k개 넘는..

힙, 우선순위큐 는 완전 이진 트리 임그래서왼쪽 자식 index: 2*i오른쪽 자식 index: 2*i +1부모 index = i/2 단 행렬에서, index 는 1부터.. leftChild of i = heap[2 * i]rightChild of i = heap[(2 * i) + 1] parent of i = heap[i // 2] 힙(Heap)의 종류힙에는 크게 두 가지 유형이 있습니다:최소 힙 (Min Heap):루트 노드에 가장 작은 값이 위치합니다.가장 작은 값이 우선순위가 가장 높으며, 가장 먼저 제거됩니다.최대 힙 (Max Heap):루트 노드에 가장 큰 값이 위치합니다.가장 큰 값이 우선순위가 가장 높으며, 가장 먼저 제거됩니다.이번 내용에서는 **최소 힙(Min Heap)**에 초점을 맞..

295. Find Median from Data Stream https://youtu.be/itmhHWaHupI?si=QWJJw3c9WUZ0gmFN class MedianFinder: # 힙에서 데이터 추가/삭제는 O(log N) 이고, 검색은 O(1) 임 # small heap 은 max heap 으로, large heap 은 min heap 으로.. # max heap 을 pop 하면, # 가장 큰값이 추출되므로 이것을 large heap으로 바로 보낼 수 있음 # 우선 small heap 에 데이터 넣고 # 발란스가 small heap 이 더 크면, small heap 의 최대갑을 large heap 으로 넣고 # 여기서 발란스는 ..