힙(Heap)

우선순위 큐(Priority Queue)

• 일정한 규칙에 의해 먼저 나가는 숫자가 정해진다.

힙(Heap)

• 힙은 주로 이진트리(Binary Tree) 기반으로 구현한다.
• 트리(tree) : 부모 - 자녀처럼 계층적인 형태를 가지는 구조이다.
• 힙은 max heap과 min heap이 있다.
• max heap : 부모노드의 키가 자식노드의 키보다 크거나 같은 트리
• min heap : 부모노드의 키가 자식노드의 키보다 작거나 같은 트리

힙의 주요 동작

• insert(value), delete() (루트노드 max or min 값이 delete 됨)

힙의 동작 방식

• 이진트리 방식으로 자식노드를 최대 두 개 갖는다.
• insert() → 맨 마지막 노드에 값 삽입 → 해당 노드의 부모 노드와 값 비교하여 재정렬
• delete() → 최상단 루트노드 삭제 → 맨 마지막 자식 노드가 빈 공간인 루트노드로 이동 → 재정렬

힙의 시간 복잡도

• insert() : O(logn)
• delete() : O(logn)
• top : O(1)
• build heap : O(n)

우선순위 큐 vs 힙

• ADT : 추상화된 데이터 타입 (구현되어 있지는 않음, 동작 방식에 대한 개념만이 정의됨)
• 데이터 구조(Data Structure)이다. (구현되어 있음)

활용 예시

힙을 파이썬으로 활용하는 방법

# 모듈 불러오기
from heapq import heappush, heappop, heapify

# 힙 생성
heap = []

# 힙 원소 추가
heappush(heap, value)

# 힙 원소 제거
heappop(heap)

# 최소값 삭제하지 않고 접근하기
heap[0]

# 기존 리스트를 힙으로 변환(heapify)
list = [4, 1, 7, 3, 8, 5]
heapify(list)

# max heap
nums = [4, 1, 7, 3, 8, 5]
heap = []
for num in nums:
  heappush(heap, (-num, num))

# 기본적으로 힙은 min heap으로 정렬하므로 음수(-)가 붙으면
# (-8, 8), (-7, 7), (-5, 5) 순으로 나타나게 됨
# index 1의 값을 출력하면 8, 7, 5, 4, 3, 1 순으로 최대값으로 정렬됨
while heap:
  print(heappop(heap)[1])

# n번째 최소값/최대값
# heap으로 만든 후 heappop() 함수를 n번 호출하면 된다.
def nth_smallest(nums, n):
  heap = []
	# heapify(nums)를 사용하면 for문 불필요
  for num in nums:
    heappush(heap, num)
    
  nth_min = None
  for _ in range(n):
    nth_min = heappop(heap)
  return nth_min

print(nth_smallest([4, 1, 7, 3, 8, 5], n))

# 힙 정렬(heap sort)
def heap_sort(nums):
  heap = []
  for num in nums:
    heappush(heap, num)

  sorted_nums = []
  while heap:
    sorted_nums.append(heappop(heap))
  return sorted_nums

프로그래머스 Level2 더 맵게

from heapq import heappush, heappop, heapify

def solution(scoville, K):
    heapify(scoville)
    answer = 0
    while scoville[0] < K:
        try:
            first_min, second_min = heappop(scoville), heappop(scoville)
            new = first_min + (second_min * 2)
            heappush(scoville, new)
            answer += 1
        except:
            return -1
    return answer

프로그래머스 Level3 이중우선순위큐

from heapq import heappop, heappush, heapify

def maxheap(heapq):
    heap = []
    max_heap = []
    
    for h in heapq:
        h = int(h)
        heappush(heap, (-h, h))
    
    while heap:
        max_heap.append(heappop(heap)[1])
    return max_heap
                
def solution(operations):
    heap = []
    for o in operations:
        string, num = o.split(' ')[0], int(o.split(' ')[1])
        if string == 'I':
            heappush(heap, num)
        elif (string == 'D') and (num == 1) and (len(heap) > 0):
            heap = maxheap(list(heap))
            heappop(heap)
        elif (string == 'D') and (num == -1) and (len(heap) > 0):
            heappop(heap)
        elif len(heap) == 0:
            pass
        
    if len(heap) == 0:
        return [0, 0]
    else:
        return max(heap), min(heap)