[자료구조] Week 4: 우선순위 큐와 힙

Day 1: 우선순위 큐의 기본 개념

• 강의 내용:
  • 우선순위 큐의 정의와 특징
    • 우선순위 큐의 개념과 용도
    • 우선순위 큐와 일반 큐의 차이점
  • 우선순위 큐의 주요 연산
    • insert, delete_min (또는 delete_max)
• 실습:
  • 기본 우선순위 큐 구현 예제

# 리스트를 사용한 간단한 우선순위 큐 구현
class PriorityQueue:
    def __init__(self):
        self.queue = []

    def insert(self, item):
        self.queue.append(item)
        self.queue.sort()  # 오름차순 정렬 (최소 우선순위 큐)

    def delete_min(self):
        if not self.is_empty():
            return self.queue.pop(0)
        return None

    def is_empty(self):
        return len(self.queue) == 0

    def display(self):
        print(self.queue)

# 우선순위 큐 사용 예제
pq = PriorityQueue()
pq.insert(3)
pq.insert(1)
pq.insert(2)
pq.display()  # [1, 2, 3]
print("Delete min:", pq.delete_min())  # Delete min: 1
pq.display()  # [2, 3]

 

Day 2: 힙의 기본 개념

• 강의 내용:
  • 힙의 정의와 특징
    • 힙의 개념과 용도
    • 완전 이진 트리 구조
  • 최대 힙과 최소 힙
    • 최대 힙과 최소 힙의 차이점
• 실습:
  • 최대 힙과 최소 힙의 개념 설명

# 힙의 개념 설명
# 최대 힙: 부모 노드가 자식 노드보다 크거나 같음
# 최소 힙: 부모 노드가 자식 노드보다 작거나 같음
# 힙의 사용 예: 힙 정렬, 우선순위 큐

# 파이썬에서 heapq 모듈을 사용하여 최소 힙 구현
import heapq

min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 2)
print("Min heap:", min_heap)  # [1, 3, 2]
print("Delete min:", heapq.heappop(min_heap))  # 1
print("Min heap after pop:", min_heap)  # [2, 3]

 

Day 3: 힙의 삽입과 삭제 연산

• 강의 내용:
  • 힙의 삽입 연산
    • 삽입 시 힙의 구조 유지
  • 힙의 삭제 연산
    • 삭제 시 힙의 구조 유지
• 실습:
  • 힙의 삽입과 삭제 연산 구현

# 최대 힙을 직접 구현하는 예제
class MaxHeap:
    def __init__(self):
        self.heap = []

    def insert(self, item):
        self.heap.append(item)
        self._heapify_up(len(self.heap) - 1)

    def delete_max(self):
        if len(self.heap) > 1:
            self._swap(0, len(self.heap) - 1)
            max_item = self.heap.pop()
            self._heapify_down(0)
        elif self.heap:
            max_item = self.heap.pop()
        else:
            max_item = None
        return max_item

    def _heapify_up(self, index):
        parent_index = (index - 1) // 2
        if index > 0 and self.heap[index] > self.heap[parent_index]:
            self._swap(index, parent_index)
            self._heapify_up(parent_index)

    def _heapify_down(self, index):
        child_index = 2 * index + 1
        if child_index < len(self.heap):
            right_child_index = child_index + 1
            if right_child_index < len(self.heap) and self.heap[right_child_index] > self.heap[child_index]:
                child_index = right_child_index
            if self.heap[index] < self.heap[child_index]:
                self._swap(index, child_index)
                self._heapify_down(child_index)

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def display(self):
        print(self.heap)

# 최대 힙 사용 예제
max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(1)
max_heap.insert(2)
max_heap.display()  # [3, 1, 2]
print("Delete max:", max_heap.delete_max())  # 3
max_heap.display()  # [2, 1]

 

Day 4: 힙 정렬

• 강의 내용:
  • 힙 정렬의 개념과 원리
    • 힙 정렬의 과정
    • 힙 정렬의 시간 복잡도
  • 힙 정렬 알고리즘 구현
• 실습:
  • 힙 정렬 구현 예제

# 힙 정렬 알고리즘 구현
def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[largest] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

# 힙 정렬 사용 예제
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print("Sorted array:", arr)  # [1, 3, 4, 5, 10]

 

Day 5: 파이썬의 heapq 모듈

• 강의 내용:
  • heapq 모듈 소개
    • heapq 모듈의 기능과 사용법
  • heapq 모듈을 사용한 우선순위 큐 구현
• 실습:
  • heapq 모듈을 사용하여 우선순위 큐 구현 예제 작성

import heapq

# heapq 모듈을 사용한 우선순위 큐 구현
class PriorityQueue:
    def __init__(self):
        self.heap = []

    def insert(self, item):
        heapq.heappush(self.heap, item)

    def delete_min(self):
        return heapq.heappop(self.heap) if self.heap else None

    def is_empty(self):
        return len(self.heap) == 0

    def display(self):
        print(self.heap)

# 우선순위 큐 사용 예제
pq = PriorityQueue()
pq.insert(3)
pq.insert(1)
pq.insert(2)
pq.display()  # [1, 3, 2]
print("Delete min:", pq.delete_min())  # Delete min: 1
pq.display()  # [2, 3]

 

Day 6: 우선순위 큐와 힙의 응용

• 강의 내용:
  • 우선순위 큐와 힙의 응용 사례
    • 작업 스케줄링
    • 다익스트라 알고리즘
  • 우선순위 큐와 힙을 사용한 알고리즘
• 실습:
  • 다익스트라 알고리즘 구현

import heapq

# 그래프를 표현하는 클래스
class Graph:
    def __init__(self):
        self.edges = {}

    def add_edge(self, from_node, to_node, weight):
        if from_node not in self.edges:
            self.edges[from_node] = []
        self.edges[from_node].append((to_node, weight))

    def dijkstra(self, start):
        pq = []
        heapq.heappush(pq, (0, start))
        distances = {start: 0}

        while pq:
            current_distance, current_node = heapq.heappop(pq)

            if current_distance > distances.get(current_node, float('inf')):
                continue

            for neighbor, weight in self.edges.get(current_node, []):
                distance = current_distance + weight
                if distance < distances.get(neighbor, float('inf')):
                    distances[neighbor] = distance
                    heapq.heappush(pq, (distance, neighbor))

        return distances

# 다익스트라 알고리즘 사용 예제
g = Graph()
g.add_edge('A', 'B', 1)
g.add_edge('A', 'C', 4)
g.add_edge('B', 'C', 2)
g.add_edge('B', 'D', 5)
g.add_edge('C', 'D', 1)
distances = g.dijkstra('A')
print("Distances:", distances)  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

 

Day 7: 종합 연습 및 프로젝트

• 강의 내용:
  • 우선순위 큐와 힙을 사용한 종합 연습 문제 풀이
    • 다양한 우선순위 큐와 힙 관련 문제
    • Q&A 세션
  • 미니 프로젝트
    • 우선순위 큐와 힙을 활용한 간단한 프로그램 구현
    • 예: 작업 스케줄링 시스템
• 실습:
  • 종합 연습 문제 풀기
  • 미니 프로젝트 작성 및 발표

# 연습 문제 1: 힙을 사용한 K번째 최소값 찾기
def find_kth_smallest(arr, k):
    heapq.heapify(arr)
    for _ in range(k - 1):
        heapq.heappop(arr)
    return heapq.heappop(arr)

arr = [7, 10, 4, 3, 20, 15]
k = 3
print(f"{k}번째 최소값:", find_kth_smallest(arr, k))  # 7

# 미니 프로젝트 예제: 작업 스케줄링 시스템
class Task:
    def __init__(self, name, priority):
        self.name = name
        self.priority = priority

    def __lt__(self, other):
        return self.priority < other.priority

class TaskScheduler:
    def __init__(self):
        self.pq = []

    def add_task(self, task):
        heapq.heappush(self.pq, task)

    def schedule(self):
        while self.pq:
            task = heapq.heappop(self.pq)
            print(f"Scheduling task: {task.name} with priority {task.priority}")

# 작업 스케줄링 시스템 사용 예제
scheduler = TaskScheduler()
scheduler.add_task(Task("Task 1", 3))
scheduler.add_task(Task("Task 2", 1))
scheduler.add_task(Task("Task 3", 2))
scheduler.schedule()
# Output:
# Scheduling task: Task 2 with priority 1
# Scheduling task: Task 3 with priority 2
# Scheduling task: Task 1 with priority 3

 

이 강의는 파이썬의 자료구조 중 우선순위 큐와 힙을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!