[비선형 자료구조] 힙(Heap) 정리 및 문제 풀이

 

1. 힙 주요 연산 

 

힙 생성(heapify): 배열에서 힙을 생성하는 프로세스, 전체 요소 검사 → O(n) 시간 복잡도

 

삽입: 기존 힙에 요소를 삽입하는 과정, O(logn) 시간 복잡도

 

삭제: 힙의 최상위 요소 혹은 우선순위가 가장 높은 요소를 삭제한 후, 나머지 요소로 다시 힙을 생성, O(logn) 시간 복잡도

 

찾기(peek): 힙에서 가장 우선순위가 높은 요소를 찾는 것, 루트 노드를 찾으면 되므로 O(1) 시간 복잡도를 가짐 

 

---

 

 

2. 파이썬에서 힙 구현 

• 파이썬에서는 heapq 라이브러리를 사용하여 힙 구현 가능
• heapq는 최소 힙을 사용

import heapq 

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

heapq.heapify(nums)
print(nums) #[0, 1, 2, 6, 3, 5, 4, 7, 8, 9]

 

• heappush를 사용하는 것 역시 heapify와 동일한 결과를 도출함 

import heapq

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

for num in nums:
    heapq.heappush(heap, num)
    
print(heap) #[0, 1, 2, 6, 3, 5, 4, 7, 8, 9]

 

---

3. 문제 풀이 

 

 

 

---

4. 문제 코드 

 

[level 1] 명예의 전당 

import heapq

def solution(k, score):
    answer = []
    h = []
    
    for sco in score:
        heapq.heappush(h, sco)
        
        if len(h) > k:
            heapq.heappop(h)
        
        answer.append(h[0])
    
    return answer

 

 

[level2] 더 맵게

import heapq

def solution(scoville, K):
    answer = 0
    f ,s = 0, 0 
    
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        if len(scoville) == 1:
            return -1
        f = heapq.heappop(scoville)
        s = heapq.heappop(scoville)
        
        heapq.heappush(scoville, f+(s*2))
        answer +=1
        
    return answer

 

 

[level 3] 야근지수 

import heapq

def solution(n, works):
    answer = 0
    
    h = []
    
    if sum(works) < n:
        return 0
    
    for w in works:
        heapq.heappush(h, -w)
    
    for _ in range(n):
        time = heapq.heappop(h)
        time +=1
        heapq.heappush(h, time)
        
    answer = sum([work**2 for work in h])
    
    return answer