힙 (Heap), 우선순위 큐(Priority Queue)

• 힙은 완전 이진 트리의 일종으로, 우선순위 큐를 구현하기 위해 사용되는 자료구조
  

heap : 특정 규칙을 갖는 완전 이진 트리

• 최대 힙: 부모 노드가 자식 노드보다 항상 크거나 같음
• 최소 힙: 부모 노드가 자식 노드보다 항상 작거나 같음

이진 트리

• 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조
• 완전 이진트리: 말단 노드를 제외하고 모든 노드가 2개의 자식을 갖고 있는 이진 트리
  
  

힙의 특징

• 힙은 각 노드가 하위 노드보다 큰(or작은) 우선 순위를 가진다.
• 최대 힙에서는 부모 노드가 자식 노드보다 항상 크고,
  최소 힙에서는 부모 노드가 자식 노드보다 항상 작다.
• 우선순위 큐 구현에 사용되는 자료구조
  우선순위 큐는 삽입 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조.

파이썬 heapq 모듈을 통해 힙을 쉽게 구현할 수 있다.

import heapq

# 최소 힙
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print(heapq.heappop(min_heap))  # 1

# 최대 힙
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -3)
print(-heapq.heappop(max_heap))  # 5

# heapq는 최소 힙을 기반으로 만들어졌기 때문에 양수를 사용하면 최소 힙
  음수를 사용하면 최대 힙을 구현할 수 있다. 

Hash Table

해시 테이블은 키(Key)를 값(Value)에 매핑할 수 있는 구조로, 데이터를 빠르게 검색, 추가, 삭제가 가능하다.

• key-value 쌍을 저장하는 자료구조
• 매우 빠른 검색, 삽입 및 삭제가 가능 O(1)의 시간 복잡도
• 해시 함수를 사용해 키를 해시 값으로 변환
• 해시함수 특징
  • 결정성 (Deterministic)
  • 고정된 출력 크기 (Fixed Output Size)
  • 빠른 계산 (Fast Computation)
  • 균일한 분포 (Uniform Distribution)
  • 충돌 저항성 (Collision Resistance)

# 해시 테이블 생성
hash_table = {}

# 삽입 (Insert)
hash_table["apple"] = "사과"
hash_table["banana"] = "바나나"
hash_table["grape"] = "포도"

print("현재 해시 테이블:", hash_table)

# 검색 (Search)
print("apple의 값:", hash_table.get("apple"))
print("banana의 값:", hash_table.get("banana"))

# 삭제 (Delete)
hash_table.pop("grape", None)
print("현재 해시 테이블:", hash_table)