[C#] 알고리즘 :: Heap과 우선순위 큐(Priority Queue) 특징 및 구현

▶참고한 링크글

https://hate-errorlog.tistory.com/4

https://chanhuiseok.github.io/posts/ds-4/

 

 

▶Heap

Heap : 여러 개의 값 중 최소값 또는 최대값을 빠르게 탐색하기 위한 완전이진트리 구조를 가진 자료구조

 

Heap의 특징

1.완전이진트리 형태

2.부모노드와 자식노드가 대소 관계가 성립된다.(반정렬상태)

3.이진탐색트리(BST)와 달리 중복된 값이 허용된다.

 

*완전이진트리 : 마지막 레벨을 제외한 모든 레벨이 모두 채워져 있고 마지막 레벨은 왼쪽부터 채워지는 트리

 

 

Heap의 종류
1.Min-Heap(최소힙)

부모노드의 키 값이 자식 노드보다 작은 구조

2.Max-Heap(최대힙)

부모노드의 키 값이 자식 노드보다 큰 구조

[중요] 종류에 상관없이 부모노드에 위치한 데이터가 가장 높은 우선순위를 가진다.

 

데이터의 삽입 

Min-Heap의 경우

1. 3의 우선순위를 가진 원소를 제일 마지막레벨에 삽입후, 대소 비교후 부모의 우선순위 값이 더 크기에 Swap 실행

2. 부모가 존재할경우 한번더 대소 비교 진행 , 부모의 우선순위 값이 더 크기에 한번더 Swap

3.  부모가 존재하기에 한번더 대소비교 진행 , 자식의 우선순위 값이 크기 때문에 루프 종료

 

?? : Min-Heap에서 우선순위가 9,10인 노드보다 8이 더 아래에 위치 해있는데요?

Heap 자료 구조는 "정렬된 트리" 아니라 "구조와 조건"을 만족하는 트리이기 때문 => 기본 구조가 완전이진트리

 

데이터의 삭제 

Min-Heap의 경우

1. 최상위 부모노드(루트노드) 삭제 , 레벨이 제일 낮은 말단의 노드를 옮김 , 그후 자식 노드들과 대소 비교 진행

8 과 3 비교시 8이 우선순위 값이 더 크기에 노드 교체 진행

2. 자식노드가 존재하는 경우 한번더 대소 비교 진행 , 값이 크기에 한번더 교체 진행

( 그림은 6으로 되어있지만 4와 교체가 되어야한다 )

 

Heap의 삭제에서는 이진 트리이기에 부모노드에서 대소 비교를 2번 진행해 줘야한다. 

자식 노드중 더 우선순위 값이 작은 값을 찾아 해당 노드와 비교를 진행한다.

(1)번에서도 3 과 5가 있으나 3이 우선순위가 더 작기에 3과 데이터 스왑이 진행된다. 

 

 

 

우선순위 큐(Priority Queue)

개요

큐에 있는 원소를 꺼낼때 넣은 순서가 아닌 우선순위가 높은(낮은) 순서로 꺼내지게 된다. 

 

특징

1. Heap 자료구조를 사용하여 효율적으로 구성 (다른 자료구조를 사용해도 됨)

2.우선순위가 같다면 일반적으로 삽입순서에 따라 처리되거나, 다른 기준을 적용 시켜 정렬 시킬 수 있다.

3.각 원소간의 중복을 허용한다.

 

 

해당 자료구조를 직접 구현하는 이유?

1.공부 목적 및 로직 파악

2.사용하는 .NET Framework 버전이 호환 안됨

https://learn.microsoft.com/ko-kr/dotnet/api/system.collections.generic.priorityqueue-2?view=net-8.0

PriorityQueue<TElement,TPriority> 클래스 (System.Collections.Generic)

해당 링크를 참고하면 

(좌) PriorityQueue를 사용 할 수 있는 버전 (우) 현재 사용자의 .NET 버전

 

 

우선순위 큐의 장점

1. 빠른 최대/최소 접근 : Heap의 루트노드에서 최대값/최소값 O(1)로 확인 가능

2. 삽입/삭제 효율적 :  삽입/삭제시 재정렬 작업이 푤이하지만 시간 복잡도가 O(log N) 임

3. 우선순위 기준 처리 용이  : 특정 작업을 순서 없이 넣어도 중요도 순으로 꺼낼 수 있음

 

우선순위 큐의 단점

1. 전체 정렬에 부적합 : Heap은 전체 정렬이 되어있지 않음 정렬이 필요한 상황에는 비효율적

2. 중간 요소 탐색 불리 : 일반 배열처럼 임의 접근 효율이 떨어짐 

3. 구조 유지 작업 필요 : 삽입/삭제시  tree구조를 유지해야하므로 재구성 비용이 존재함

 

우선순위 큐 시간 복잡도

연산	시간복잡도	설명
Enqueue	O(log n)	가장 끝에 삽입 후 ,Heapify Up
Dequeue	O(log n)	루트를 제거하고 , Heapify Down
Peek	O(1)	루트를 바로 반환

 

사용 예시 

1. 턴 기반 게임의 행동 우선순위 처리 ex) 포켓몬 턴제 전투

2. 길찾기 알고리즘에 사용 ex) A*알고리즘

 

구현 방법 (Min-Heap 기준)

1. 우선순위 큐에서 필요한 기능 기획

-원소(데이터)를 담을 컨테이너 필요 => List 사용

우선순위 큐에는 2개의 변수가 필요함 , 데이터를 보관할 변수 , 우선순위를 표시할 변수 => 튜플 자료형 사용

using System;
using System.Collections.Generic;

public class PriorityQueue<TElement, TPriority> where TPriority : IComparable<TPriority>
{
    //프로퍼티
    public List<(TElement element, TPriority priority)> Heap => _heap;
    public int Count => _heap.Count;
    
    private readonly List<(TElement element, TPriority priority)> _heap = new List<(TElement, TPriority)>();  
}

우선 자료구조이기에 제네릭 클래스로 생성하고 2개의 T를 생성한다.

TElement : 실제 저장할 데이터 단위

TPriority : 해당 데이터의 우선순위

TPrioirty는 대소 비교가 가능하기에 제약 조건으로 IComparaable<TPriority> 걸음

 

우선순위 큐를 List로 생성하였기에 배열 기반의 완전 이진트리에서 부모/자식 인덱스를 찾는 공식이 필요하다.

관계	계산식
부모 -> 왼쪽 자식	left = n * 2 +1
부모 -> 오른쪽 자식	right = n * 2 + 2
자식 -> 부모	parent = (n-1) / 2

여기서 n은 자기 자신의 Index를 말하는 것이다.

 

-우선순위 6번의 부모의 인덱스 = ( 3 -1 ) / 2 = 1

-우선순위 3번 노드의 왼쪽자식와 오른쪽 자식의 인덱스

왼쪽자식  = 1 * 2 + 1 = 3

오른쪽자식  = 1 * 2 + 2 = 4

 

2.요소 삽입 구현(Enqueue)

  public bool EnQueue(TElement element, TPriority priority)
  {
      // 마지막 위치에 원소 추가
      _heap.Add((element, priority));
      var index = _heap.Count - 1;

      while (index > 0)
      {
          //부모 노드의 인덱스 구해오기
          var parent = (index - 1) / 2;

          // 현재 노드의 우선순위가 부모보다 크거나 같으면 더이상 위로 올릴 필요 없음
          // Min-Heap 기준
          if (_heap[index].priority.CompareTo(_heap[parent].priority) >= 0)
          {
              return true;
          }

          // 아니라면 부모와 자식을 스왑
          (_heap[parent], _heap[index]) = (_heap[index], _heap[parent]);
          index = parent;
      }

      return false;
  }

 

3.요소 삭제 구현(DeQueue)

  public bool TryDequeue(out TElement element, out TPriority priority)
  {
      if (_heap.Count <= 0)
      {
          element = default;
          priority = default;
          return false;
      }

      // 루트 요소 반환(최상위 부모노드 삭제)
      element = _heap[0].element;
      priority = _heap[0].priority;

      // 마지막 요소를 루트(취상위 부모)에 위치시키고, 힙 크기를 줄임
      var lastElement = _heap[^1];//제일 마지막 노드를 복사
      _heap[0] = lastElement;
      _heap.RemoveAt(_heap.Count - 1);

      //정렬 시작
      var index = 0;
      var count = _heap.Count;

      while (true)
      {
          //자식의 인덱스를 구함
          var left = index * 2 + 1;
          var right = index * 2 + 2;
          var current = index;

  //여기서 왼쪽과 오른쪽 두 자식과 모두 비교하여 더 “우선순위가 높은”자식과 스왑해야 하므로, 두 자식과 모두 비교
          // 좌측 자식의 우선순위가 현재 우선순위보다 낮다면
          if (left < count && _heap[left].priority.CompareTo(_heap[current].priority) < 0)
          {
              current = left;
          }
			
        
          // 우측 자식의 우선순위가 현재 우선순위보다 낮다면
          if (right < count && _heap[right].priority.CompareTo(_heap[current].priority) < 0)
          {
              current = right;
          }

          //두 조건 다 만족하지 못한다면
          if (current == index)
          {
              return true;
          }

          // Swap
          (_heap[current], _heap[index]) = (_heap[index], _heap[current]);
          index = current;
      }

  }