👨‍🏫 들어가며


안녕하세요! 강창민 튜터입니다. 어느새 마지막 알고리즘 중급 강의 시간이에요.

이번 강의에서는 트리의 특수 형태이자 여러분들이 많이 들어보셨을 힙에 대해서 살펴보겠습니다. 또한, 힙과 힙 정렬에 대해서 살펴보고 힙과 관계가 깊은 다익스트라 알고리즘에 대해서 살펴볼게요!

힙이 뭐에요?


힙은 **우선순위 큐(Priority Queue)**를 구현하는 데 주로 사용되는 자료구조에요. 힙에는 **최대 힙(Max Heap)**과 **최소 힙(Min Heap)**이 있는데요. 최대 힙은 항상 가장 큰 값을, 최소 힙은 항상 가장 작은 값을 루트에 위치하게 합니다.

조금 더 정리를 해보자면요.

스크린샷 2024-10-25 오후 2.16.48.png

  1. 최대 힙(Max Heap)
    1. 부모 노드가 항상 자식 노드보다 큰 값을 가집니다.
    2. 루트 노드는 항상 최대값이 돼요.
  2. 최소 힙(Min Heap)
    1. 부모 노드가 자식 노드보다 작은 값을 가져요.
    2. 루트 노드는 최소값이 됩니다.

이러한 특성이 있는 힙은 주로 우선순위가 있는 작업을 처리할 때 많이 사용돼요. 위에서 제가 우선순위 큐에 대해서 잠깐 얘기했었죠. 이 우선순위 큐는 일반적인 큐와 달리 각 요소에 우선순위가 있어 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조에요. 예를 들어, 운영 체제의 작업 스케줄러에서 긴급한 작업이 먼저 처리되도록 할 때 우선순위 큐를 사용해요. 힙은 이 우선순위 큐를 효율적으로 구현하는 데 사용됩니다.

힙에서 새로운 자식이 추가될 때?