👱‍♀️ ansohxxn

👱‍♀️ ansohxxn

개인적인 필기 노트

Chapter 5-2. 힙 트리 & 우선순위 큐

Date:     Updated:

카테고리:

태그:

인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click

Chapter 5. 트리

🚖 힙

이진 트리

이진 트리 👉 모든 노드들이 자식 노드를 최대 2 개까지만 가지는 트리


이진 검색 트리

image

다음과 같은 조건이 적용된 이진트리.

  1. 왼쪽을 타고 가면 현재 값보다 작다. 👉 왼쪽 자식 노드는 부모 노드보다 작아야 한다.
    • 루트를 기준으로 왼쪽 서브트리 노드의 데이터들은 전부 루트보다 작은 값을 가진다.
  2. 오른쪽을 타고 가면 현재 값보다 크다. 👉 오른쪽 자식 노드는 부모 노드보다 커야 한다.
    • 루트를 기준으로 오른쪽 서브 트리 노드의 데이터들은 전부 루트보다 큰 값을 가진다.

이진 검색 트리는 이러한 구성을 가지기 때문에 해당 데이터를 가진 노드를 검색하는게 빠르다. 찾으려는 값보다 작으면 왼쪽으로 내려가고, 찾으려는 값보다 크면 오른쪽으로 내려가면 되기 때문.

  • 이진 검색 트리에 값을 추가할 때
    • 그냥 무식하게 추가하면 한쪽으로 기울어져서 균형이 깨진다.
      • 예를 들어 트리에 있는 노드들보다 큰 값만 계속해서 추가한다면 트리가 한쪽으로만 쭉 길어질 수 있음. 이러면 리스트 같은 선형 자료구조와 다를게 없어져 이진 검색트리의 빠른 검색 이점이 사라질 수 있다.
    • 👉 추가, 삭제시, 트리 재배치를 통해 균형을 유지하는 것이 과제

image


힙 트리 ✨

다음과 같은 조건이 적용된 이진트리.

이진 검색트리보단 제약 수준이 낮다. 이진 검색트리와 달리 양쪽 자식간에는 특별한 조건이 없음.

image

  • 힙 트리
    • 조건 1️⃣
      • max heap 부모 노드가 가진 값은 항상 자식 노드가 가진 값보다 크다. 👉 그냥 부모가 자식들보다 크면 된다.
        • 이 힙 트리의 루트 값은 언제나 최대값이다.
      • min heap 인 경우엔 부모 노드가 가진 값은 항상 자식 노드가 가진 값보다 작다. 👉 그냥 부모가 자식들보다 작으면 된다.
        • 이 힙 트리의 루트 값은 언제나 최소값이다.
    • 제약 조건
      1. 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있다.
      2. 마지막 레벨에 노드가 있을 때는, 항상 왼쪽부터 순서대로 채워야 한다.
    • 조건 2️⃣
      • 이 제약 조건 때문에 노드의 개수를 알면, 트리 구조는 무조건 확정할 수 있다.
        • 만약 데이터 개수가 5 개인 경우, 힙트리 구조는 아래와 같은 구조로 확정 된다.
        • 따라서 힙 구조는 데이터 개수만 알면 언제나 확정되기 때문에 배열을 이용해서 힙 구조를 바로 표현할 수 있다.
          • 인덱스 i 노드의 왼쪽 자식 노드의 인덱스는 2 * i + 1
          • 인덱스 i 노드의 왼쪽 자식 노드의 인덱스는 2 * i + 2
          • 인덱스 i 노드의 부모 노드의 인덱스는 (i - 1) / 2 (정수이므로 소수점 버림. 몫만.)

힙 트리는 배열로 구현할 수 있다.

image

추가하기
  1. 조건 2️⃣ 에 의하여 👉 노드 개수를 알면 트리 구조를 무조건 확정지을 수 있으므로 우선 트리 구조부터 맞춰준다.
    • 마지막 레벨에 추가하되 왼쪽에서부터 순서대로 채워넣기
  2. 조건 1️⃣ 에 의하여 👉 부모 노드는 항상 자식 노드보다 커야 하므로 이 조건이 만족 될 때까지 자리를 서로 뒤 바꿔 올라가게 한다.

image

최대값 꺼내기
  1. 최대값을 먼저 제거한다. 👉 힙 트리 모양이 망가지므로 다시 재정비 해주어야 한다.
  2. 조건 2️⃣ 에 의하여 제일 마지막에 위치한 데이터를 빈 루트 자리로 옮긴다.
  3. 조건 1️⃣ 에 의하여 👉 부모 노드는 항상 자식 노드보다 커야 하므로 이 조건이 만족 될 때까지 자리를 서로 뒤 바꿔 내려가게 한다.

image


🚖 우선순위 큐 구현

using System;
using System.Collections.Generic;

namespace Excercise
{
    class PriorityQueue
    {
        // 힙 트리는 배열로 관리할 수 있다.
        List<int> _heap = new List<int>();

        public void Push(int data)
        {
            // 힙의 맨 끝에 새로운 데이터를 삽입한다.
            _heap.Add(data);

            int now = _heap.Count - 1;  // 추가한 노드의 위치. 힙의 맨 끝에서 시작.
            
            // 위로 도장 깨기 시작
            while (now > 0)
            {
                int next = (now - 1) / 2;  // 부모 노드
                if (_heap[now] < _heap[next])  // 부모 노드와 비교
                    break;

                // 두 값을 서로 자리 바꿈
                int temp = _heap[now];
                _heap[now] = _heap[next];
                _heap[next] = temp;

                // 검사 위치로 이동한다.
                now = next;
            }
        }

        public int Pop()  // 최대값(루트)을 뽑아낸다.
        {
            // 반환할 데이터를 따로 저장
            int ret = _heap[0];

            // 마지막 데이터를 루트로 이동시킨다.
            int lastIndex = _heap.Count - 1;
            _heap[0] = _heap[lastIndex];
            _heap.RemoveAt(lastIndex);
            lastIndex--;

            // 아래로 도장 깨기 시작
            int now = 0;
            while(true)
            {
                int left = 2 * now + 1;
                int right = 2 * now + 2;

                int next = now;
                // 왼쪽 값이 현재값보다 크면, 왼쪽으로 이동
                if (left <= lastIndex && _heap[next] < _heap[left])
                    next = left;
                // 오른쪽 값이 현재값(왼쪽 이동 포함)보다 크면, 오른쪽으로 이동
                if (right <= lastIndex && _heap[next] < _heap[right])
                    next = right;

                // 왼쪽/오른쪽 모두 현재값보다 작으면 종료
                if (next == now)
                    break;

                // 두 값 서로 자리 바꿈
                int temp = _heap[now];
                _heap[now] = _heap[next];
                _heap[next] = temp;

                // 검사 위치로 이동한다.
                now = next;
            }

            return ret;
        }

        public int Count()
        {
            return _heap.Count;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            PriorityQueue q = new PriorityQueue();
            q.Push(20);
            q.Push(10);
            q.Push(30);
            q.Push(90);
            q.Push(40);

            while (q.Count() > 0) // 90 40 30 20 10 출력
            {
                Console.WriteLine(q.Pop());  
            }
        }
    }
}

우선순위 큐 자료구조는 힙 트리를 사용한다.

  • 우선순위 큐
    • 들어간지 가장 오래된게 나오는 선입선출 방식인 일반 큐와 달리, 들어간 순서와는 상관없이 가장 큰 값을 가진 데이터가 빠져나오게 된다.
      • 👉 Max Heap Tree를 우선순위 큐 자료구조로서 사용하면 된다.
        • 루트 노드는 언제나 최대값이 오도록 힙 트리 구조 유지.
        • 데이터를 뽑을 땐 루트 노드 데이터를 뽑으면 됨.
      • Min Heap 은 Max Heap Tree로 구현된 우선순위 큐에 원하는 데이터들을 - 붙여 음수로 넣은 후 꺼내고 나서 다시 -을 붙여 원래대로 양수로 만들어 사용할 수도 있다.
        • 음수는 절대값이 작은게 큰 것이라는 점을 이용하여.
  • 힙 트리는 배열로 나타낼 수 있다. 
    List<int> _heap = new List<int>();

Push : 우선순위 큐에 노드 추가

힙 트리의 추가 과정 그림 위에서 참고!

        public void Push(int data)
        {
            // 힙의 맨 끝에 새로운 데이터를 삽입한다.
            _heap.Add(data);

            int now = _heap.Count - 1;  // 추가한 노드의 위치. 힙의 맨 끝에서 시작.
            
            // 위로 도장 깨기 시작
            while (now > 0)
            {
                int next = (now - 1) / 2;  // 부모 노드
                if (_heap[now] < _heap[next])  // 부모 노드와 비교
                    break;

                // 두 값을 서로 자리 바꿈
                int temp = _heap[now];
                _heap[now] = _heap[next];
                _heap[next] = temp;

                // 검사 위치로 이동한다.
                now = next;
            }
        }

삽입은 아래에서 부터 위로 올라가며 스왑해나간다.

  • 새로운 데이터는 힙의 맨 끝에 삽입한다.
    • 힙 트리는 배열로 관리되므로 배열에 추가하면 된다.
  • now에는 처음에 추가한 데이터의 바뀌어 가는 인덱스
    • _heap.Count - 1 에서 시작
  • 부모 > 자식 관계가 완성될 때까지 위로 올라가며 추가한 데이터를 스왑해 나간다. 제자리를 찾기 위한 과정
    • next는 현재의 now의 부모
    • _heap[now] < _heap[next]
      • 힙 트리 조건(부모 > 자식)을 만족하는 제 자리를 찾았으니 끝냄
    • _heap[now] >= _heap[next]
      • 자식이 부모보다 더 크므로 안된다. 제 자리를 찾아 올라가야 하므로 둘이 스왑한다.
        • 스왑한 후
        • 위로 올라간다. now = next

Pop : 우선순위 큐에서 최대값 뽑기 👉 루트 노드 삭제

        public int Pop()  // 최대값(루트)을 뽑아낸다.
        {
            // 반환할 데이터를 따로 저장
            int ret = _heap[0];

            // 마지막 데이터를 루트로 이동시킨다.
            int lastIndex = _heap.Count - 1;
            _heap[0] = _heap[lastIndex];
            _heap.RemoveAt(lastIndex);
            lastIndex--;

            // 아래로 도장 깨기 시작
            int now = 0;
            while(true)
            {
                int left = 2 * now + 1;
                int right = 2 * now + 2;

                int next = now;
                // 왼쪽 값이 현재값보다 크면, 왼쪽으로 이동
                if (left <= lastIndex && _heap[next] < _heap[left])
                    next = left;
                // 오른쪽 값이 현재값(왼쪽 이동 포함)보다 크면, 오른쪽으로 이동
                if (right <= lastIndex && _heap[next] < _heap[right])
                    next = right;

                // 왼쪽/오른쪽 모두 현재값보다 작으면 종료
                if (next == now)
                    break;

                // 두 값 서로 자리 바꿈
                int temp = _heap[now];
                _heap[now] = _heap[next];
                _heap[next] = temp;

                // 검사 위치로 이동한다.
                now = next;
            }

            return ret;
        }

힙 트리의 루트 노드는 늘 최대값이다. 모든 부모 노드는 자식 노드들보다 크기 때문이다.

루트 노드 삭제 및 리턴인 Pop 은 아래로 내려가며 스왑해나간다.

  • 루트 노드 _heap[0] 를 리턴해야 하니까 삭제 전에 ret에 보존해두기
    • 나중에 이를 리턴하고 끝낸다.
  • 마지막 데이터를 빈 루트 노드 자리로 이동시킨다.
    • 루트 노드에 마지막 노드 복사
    • 마지막 노드 삭제
  • lastIndex는 힙 트리의 마지막 인덱스
  • now는 루트 노드에 올라오게 된 마지막 데이터가 제 자리를 찾아가는 과정마다 위치하게 될 인덱스를 저장
    • 루트에서 시작하므로 0 에서 시작
  • next에 다음에 내려갈 위치
  • 현재 now의 왼쪽 자식 left
  • 현재 now의 오른쪽 자식 right
  • 루트에 올라오게 된 마지막 데이터를 부모 > 자식 관계가 완성될 때까지 아래로 내려가며 스왑해 나간다. 제자리를 찾기 위한 과정
    • 인덱스를 넘지 않기 위해 left, right가 lastIndex 보다 작은지를 검사
    • 왼쪽 자식이 더 크다면 next를 left로 업데이트
    • 오른쪽 자식이 더 크다면 next를 right로 업데이트
      • 왼쪽 자식보다 오른쪽 자식이 더 크다면 next는 오른쪽 자식으로 또 업데이트 된다.
      • else if 가 아닌 그냥 if 이기 때문에
  • next가 업데이트 되지 않아 여전히 now라면 왼쪽 자식 오른쪽 자식 둘 다 현재 값보다 작다는 의미이므로 제자리를 찾았으니 저장해두었던 예전 루트 노드 ret을 리턴하고 종료.
  • 스왑한 후 아래로 내려간다. now = next

힙 트리(우선순위 큐)의 추가/삭제 연산은 \(O(logN)\) 시간 복잡도를 가진다. 즉, 트리의 높이에 따라 시간 복잡도가 결정 된다. 타고 내려가고 타고 올라가기 때문에.

Count

        public int Count()
        {
            return _heap.Count;
        }

우선순위 큐의 데이터 노드 개수는 힙 배열의 크기와 같음.


🚖 제네릭한 우선순위 큐 구현

using System;
using System.Collections.Generic;

namespace Excercise
{
    
    class Knight : IComparable<Knight>
    {
        public int id { get; set; }

        public int CompareTo(Knight other)
        {
            // id 멤버를 기준으로 크기를 비교
            if (id == other.id)
                return 0;
            return id > other.id ? 1 : -1;
        }
    }
    
    class PriorityQueue<T> where T : IComparable<T>
    {
        // 힙 트리는 배열로 관리할 수 있다.
        List<T> _heap = new List<T>();

        public void Push(T data)
        {
            // 힙의 맨 끝에 새로운 데이터를 삽입한다.
            _heap.Add(data);

            int now = _heap.Count - 1;  // 추가한 노드의 위치. 힙의 맨 끝에서 시작.
            
            // 위로 도장 깨기 시작
            while (now > 0)
            {
                int next = (now - 1) / 2;  // 부모 노드
                if (_heap[now].CompareTo(_heap[next]) < 0)  // 부모 노드와 비교
                    break;

                // 두 값을 서로 자리 바꿈
                T temp = _heap[now];
                _heap[now] = _heap[next];
                _heap[next] = temp;

                // 검사 위치로 이동한다.
                now = next;
            }
        }

        public T Pop()  // 최대값(루트)을 뽑아낸다.
        {
            // 반환할 데이터를 따로 저장
            T ret = _heap[0];

            // 마지막 데이터를 루트로 이동시킨다.
            int lastIndex = _heap.Count - 1;
            _heap[0] = _heap[lastIndex];
            _heap.RemoveAt(lastIndex);
            lastIndex--;

            // 아래로 도장 깨기 시작
            int now = 0;
            while(true)
            {
                int left = 2 * now + 1;
                int right = 2 * now + 2;

                int next = now;
                // 왼쪽 값이 현재값보다 크면, 왼쪽으로 이동
                if (left <= lastIndex && _heap[next].CompareTo(_heap[left]) < 0)
                    next = left;
                // 오른쪽 값이 현재값(왼쪽 이동 포함)보다 크면, 오른쪽으로 이동
                if (right <= lastIndex && _heap[next].CompareTo(_heap[right]) < 0)
                    next = right;

                // 왼쪽/오른쪽 모두 현재값보다 작으면 종료
                if (next == now)
                    break;

                // 두 값 서로 자리 바꿈
                T temp = _heap[now];
                _heap[now] = _heap[next];
                _heap[next] = temp;

                // 검사 위치로 이동한다.
                now = next;
            }

            return ret;
        }

        public int Count()
        {
            return _heap.Count;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            PriorityQueue<Knight> q = new PriorityQueue<Knight>();
            q.Push(new Knight() { id = 20 });
            q.Push(new Knight() { id = 10 });
            q.Push(new Knight() { id = 30 });
            q.Push(new Knight() { id = 90 });
            q.Push(new Knight() { id = 40 });

            while (q.Count() > 0) // 90 40 30 20 10 출력
            {
                Console.WriteLine(q.Pop());  
            }
        }
    }
}

IComparable<T> 인터페이스를 상속 받으면 CompareTo 비교 함수를 구현해야 한다. int 같은 기본 데이터 타입이 아닌 사용자 정의 객체 타입이라면 비교할 기준을 따로 마련해 주어야 우선순위 큐에 넣을 수 있다. (우선 순위 큐 자체가 비교와 비교를 거듭하여 항상 부모 > 자식 관계를 유지하게 하는 자료구조이므로)


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

댓글남기기

참고