[TIL] 내일배움캠프 72일차_[Python] 힙(Heap) 자료구조

👀Today I Learn

힙(Heap) 자료구조란?

• 힙(Heap)은 완전 이진 트리(Complete Binary Tree) 형태를 가지면서, 부모 노드와 자식 노드 간의 특정한 우선순위 관계를 유지하는 자료구조
• 힙은 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나뉨
  • 최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같음
  • 최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같음

• 힙은 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용됨

  자료구조	삭제되는 요소
  스택(Stack)	가장 최근에 들어온 데이터
  큐(Queue)	가장 먼저 들어온 데이터
  우선순위 큐(Priority Queue)	가장 우선순위가 높은 데이터

사용되는 곳

• 힙은 다양한 알고리즘과 시스템에서 사용됨

  1. 우선순위 큐(Priority Queue)
     • 네트워크 패킷 스케줄링
     • 운영체제의 작업 스케줄링
  2. 최소 신장 트리(MST) 알고리즘 (Prim’s Algorithm)
  3. 다익스트라 최단 경로 알고리즘
  4. 정렬 알고리즘 (힙 정렬, Heap Sort)
  5. 이벤트 드리븐 시뮬레이션(Event-driven Simulation)

Python에서 힙 사용하기

• Python에서는 heapq 모듈을 사용하여 힙을 쉽게 다룰 수 있음

1. 최소 힙 구현

• Python의 heapq는 최소 힙(Min Heap)을 기본적으로 제공

    import heapq
  
    # 최소 힙 생성
    min_heap = []
    heapq.heappush(min_heap, 10)
    heapq.heappush(min_heap, 5)
    heapq.heappush(min_heap, 20)
  
    print(heapq.heappop(min_heap))  # 가장 작은 값 출력 (5)
    print(heapq.heappop(min_heap))  # 10
    print(heapq.heappop(min_heap))  # 20
  

2. 최대 힙 구현(음수 활용)

• Python heapq 모듈은 최대 힙을 기본적으로 지원하지 않지만, 음수 값을 사용하여 최대 힙처럼 동작하게 만들 수 있음

    import heapq
  
    max_heap = []
    heapq.heappush(max_heap, -10)
    heapq.heappush(max_heap, -5)
    heapq.heappush(max_heap, -20)
  
    print(-heapq.heappop(max_heap))  # 가장 큰 값 출력 (20)
    print(-heapq.heappop(max_heap))  # 10
    print(-heapq.heappop(max_heap))  # 5
  

  • 음수 값을 삽입하고, 꺼낼 때 다시 음수로 변환하면 최대 힙처럼 동작

3. 힙 정렬(Heap Sort) 구현

• 힙 정렬은 힙을 활용한 정렬 알고리즘으로, O(N log N)의 시간 복잡도를 가짐

    import heapq
  
    def heap_sort(iterable):
        heap = []
        for value in iterable:
            heapq.heappush(heap, value)
          
        sorted_list = [heapq.heappop(heap) for _ in range(len(heap))]
        return sorted_list
  
    arr = [3, 1, 4, 1, 5, 9, 2, 6, 5]
    sorted_arr = heap_sort(arr)
    print(sorted_arr)  # [1, 1, 2, 3, 4, 5, 5, 6, 9]
  

💡Today I Thought

오늘의 체크리스트

• 알고리즘 코드카타 331
• SQL 코드카타 106
• Streamlit 특강 : 14시
• AI 모델 활용 4주차 강의 듣기
• 스탠다드반 수업 복습
• TIL 작성

회고

 오늘 알고리즘 코드카타를 하다가 힙 알고리즘이 나왔다. 다른 알고리즘은 두세번 읽으면 이해가 됐는데, 이건 아직도 모르겠.. 헷갈리고..🫠 오늘도 무지렁이가 되..😢