Heap, Hash Table

• 힙(heap)과 해시 테이블(hash)의 개념을 이해하고, 파이썬에서 자료구조를 구현
• 각 자료구조의 특성을 파악하고, 실제 문제 해결에 활용
• 자료구조를 활용한 알고리즘 문제를 해결

 

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

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

 

• 힙(heap)은 특정 규칙을 갖는 완전 이진 트리
  • 최대 힙: 부모 노드가 자식 노드보다 항상 크거나 같음
  • 최소 힙: 부모 노드가 자식 노드보다 항상 작거나 같음
• 이진 트리
  • 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조
  • 완전 이진트리: 말단 노드를 제외하고 모든 노드가 2개의 자식을 갖고 있는 이진트리

 

 

 

힙의 특성

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

힙(Heap) - 파이썬에서는 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

 

 

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

 

• 키와 값의 쌍을 저장하는 자료구조
• 매우 빠른 검색, 삽입 및 삭제가 가능 O(1)의 시간 복잡도
• 해시함수(Hash Function)를 사용하여 키를 해시값(Hash Value)로 변환

 

해시함수(Hash Function)

def hash_function(key):
    return key % 10

def main():
    members = [None] * 10
    # Key
    no = 14
    # Input
    members[hash_function(no)] = "홍길동"
    # Get
    print(members[hash_function(no)])

• 입력된 키를 해시 값으로 변환하는 함수
• 대부분 O(1)에 접근 가능한 인덱스를 반환
• 해시함수 특징
  • 결정성 (Deterministic)
  • 고정된 출력 크기 (Fixed Output Size)
  • 빠른 계산 (Fast Computation)
  • 균일한 분포 (Uniform Distribution)
  • 충돌 저항성 (Collision Resistance)

 

 

총돌관리(Collision Handling)

• 해시 함수는 서로 다른 두 키가 동일한 해시 값을 반환 시 충돌(Collision)
• 체이닝(Chaining): 배열의 각 인덱스에 충돌된 모든 요소를 저장
• 오픈 어드레싱(Open Addressing): 충돌이 발생하면 다른 빈 슬롯을 찾아 값을 저장
  • 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등

 

코드

파이썬에서는 dict 딕셔너리를 사용하여 해시 테이블을 구현

# 해시 테이블 생성
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)

 

 

 

 

연습문제

힙 : https://www.acmicpc.net/problem/2075

해시 : https://www.acmicpc.net/problem/10816