You are viewing a single comment's thread. Return to all comments →
class MinHeap: def __init__(self, arr=None): self.heap = arr if arr is not None else [] if arr: self.heapify() def heapify(self): for i in range(len(self.heap) // 2 - 1, -1, -1): self._sift_down(i) def heappush(self, item): self.heap.append(item) self._sift_up(len(self.heap)-1) def heappop(self): if len(self.heap) == 1: return self.heap.pop() min_num = self.heap[0] self.heap[0] = self.heap.pop() self._sift_down(0) return min_num def _sift_down(self, idx): heap = self.heap size = len(heap) while True: l_idx, r_idx, min_idx = 2*idx+1, 2*idx+2, idx if l_idx < size and heap[l_idx] < heap[min_idx]: min_idx = l_idx if r_idx < size and heap[r_idx] < heap[min_idx]: min_idx = r_idx if min_idx != idx: heap[idx], heap[min_idx] = heap[min_idx], heap[idx] idx = min_idx else: break def _sift_up(self, idx): heap = self.heap item = heap[idx] while idx > 0: u_idx = (idx-1)//2 if item < heap[u_idx]: heap[idx] = heap[u_idx] idx = u_idx else: break heap[idx] = item def cookies(k, A): heapq = MinHeap(A) count = 0 while len(A) > 1: a = heapq.heappop() if a >= k: return count b = heapq.heappop() heapq.heappush(a + 2*b) count += 1 return -1 if A[0] < k else count
Seems like cookies are disabled on this browser, please enable them to open this website
Jesse and Cookies
You are viewing a single comment's thread. Return to all comments →