heap

find_mid.py

import heapq

def find_mid(arr):
    '''
    leetcode 295
    '''
    mid = []
    small = [] # 최대힙
    large = [] # 최소힙
    
    for i in range(len(arr)):
        
        # 중간값보다 작거나 같은 수 최대힙에 저장, 큰 수 최소힙에 저장
        if not small or not large:
            heapq.heappush(small, -arr[i])
        elif arr[i] <= -small[0]:
            heapq.heappush(small, -arr[i])
        else:
            heapq.heappush(large, arr[i])
        
        # 최대힙이 최소힙의 개수보다 1개 더 많거나 같게 유지
        if len(small) - len(large) > 1:
            heapq.heappush(large, -heapq.heappop(small))
        elif len(small) < len(large):
            heapq.heappush(small, -heapq.heappop(large))
            
        mid.append(-small[0])
    return mid
  
print([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

get_min_force.py

import heapq

def get_min_force(weights) :
    '''
    leetcode 1046 변형
    n개의 점토를 하나로 합치기 위해 필요한 힘의 합의 최솟값을 반환하는 함수를 작성하세요.
    '''

    power_sum = 0
    h = []
    for i in weights:
        heapq.heappush(h, i)
        
    while len(h) > 1:
        power = 0
        x = heapq.heappop(h)
        y = heapq.heappop(h)
        power = x + y
        power_sum += power
        heapq.heappush(h, power)

    return power_sum
    
print(get_min_force([1, 5, 7, 3]))

get_order.py

import heapq

def get_order(tasks):
    '''
    leetcode 1834. single thread cpu
    '''
    for i, t in enumerate(tasks):
        t.append(i)
    tasks.sort(key = lambda x: x[0])
    
    res, minHeap = [], []
    i, time = 0, tasks[0][0]
    while minHeap or i < len(tasks):
        while i < len(tasks) and time >= tasks[i][0]:
            heapq.heappush(minHeap, [tasks[i][1], tasks[i][1]])
            i += 1
        if not minHeap:
            time = tasks[i][0]
        else:
            procTime, index = heapq.heappop(minHeap)
            time += procTime
            res.append(index)
    return(res)
'''
bisect로 이진 탐색 구현 
bisect_left: 찾는 요소 왼쪽 인덱스
bisect_right: 찾는 요소 쪽 인덱스
'''
from bisect import bisect_left, bisect_right

nums = [0,1,2,3,4,5,6,7,8,9]
n = 5

print(bisect_left(nums, n))
print(bisect_right(nums, n))