Part 2-5-2. 트리 : 힙 트리, 우선순위 큐

공부/인프런 - Rookiss

Part 2-5-2. 트리 : 힙 트리, 우선순위 큐

셩잇님 2023. 8. 10. 15:09

힙

이진 트리

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

이진 트리의 종류

1. 이진 검색 트리 (Binary Search Tree)
항상 왼쪽 자식은 나보다 작고 오른쪽 자식은 나보다 크다.

2. 힙 트리 (Heap Tree)
Max Heap Tree : 항상 부모가 자식보다 크다. 따라서 루트는 최대값이다.
Min Heap Tree : 항상 부모가 자식보다 작다. 따라서 루트는 최소값이다.

[이진 트리]

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

1. 왼쪽을 타고 가면 현재 값보다 작다. 👉 왼쪽 자식 노드는 부모 노드보다 작아야 한다.

루트를 기준으로 왼쪽 서브트리 노드의 데이터들은 전부 루트보다 작은 값을 가진다.

2. 오른쪽을 타고 가면 현재 값보다 크다. 👉 오른쪽 자식 노드는 부모 노드보다 커야 한다.

루트를 기준으로 오른쪽 서브 트리 노드의 데이터들은 전부 루트보다 큰 값을 가진다.

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

이진 검색 트리에 값을 추가할 때

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

[힙 트리]

조건 1️⃣

max heap 부모 노드가 가진 값은 항상 자식 노드가 가진 값보다 크다. 👉 그냥 부모가 자식들보다 크면 된다. (이 힙 트리의 루트 값은 언제나 최대값이다.)
min heap 인 경우엔 부모 노드가 가진 값은 항상 자식 노드가 가진 값보다 작다. 👉 그냥 부모가 자식들보다 작으면 된다. (이 힙 트리의 루트 값은 언제나 최소값이다.)

제약 조건

마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있다.
마지막 레벨에 노드가 있을 때는, 항상 왼쪽부터 순서대로 채워야 한다.

조건 2️⃣
이러한 제약 조건 때문에 노드의 개수를 알면, 트리 구조는 무조건 확정할 수 있다.

만약 데이터 개수가 5 개인 경우, 힙트리 구조는 아래와 같은 구조로 확정 된다. 따라서 힙 구조는 데이터 개수만 알면 언제나 확정되기 때문에 배열을 이용해서 힙 구조를 바로 표현할 수 있다.
인덱스 i 노드의 왼쪽 자식 노드의 인덱스는 2 * i + 1
인덱스 i 노드의 왼쪽 자식 노드의 인덱스는 2 * i + 2
인덱스 i 노드의 부모 노드의 인덱스는 (i - 1) / 2 (정수이므로 소수점 버림. 몫만.)

[배열로 구현하는 힙 트리]

[값 추가하기]

1. 조건 2️⃣ 에 의하여 👉 노드 개수를 알면 트리 구조를 무조건 확정지을 수 있으므로 우선 트리 구조부터 맞춰준다. (마지막 레벨에 추가하되 왼쪽에서부터 순서대로 채워넣기)

2. 조건 1️⃣ 에 의하여 👉 부모 노드는 항상 자식 노드보다 커야 하므로 이 조건이 만족 될 때까지 자리를 서로 뒤 바꿔 올라가게 한다.

[최대값 꺼내기 (=루트노드 삭제하기)]

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

우선순위 큐 구현

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;
            }
        }

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

1. 새로운 데이터는 힙의 맨 끝에 삽입한다. 힙 트리는 배열로 관리되므로 배열에 추가하면 된다.

2. now에는 처음에 추가한 데이터의 바뀌어 가는 인덱스 (_heap.Count - 1 에서 시작)

3. 부모 > 자식 관계가 완성될 때까지 위로 올라가며 추가한 데이터를 스왑해 나간다. 제자리를 찾기 위한 과정

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은 Push와 반대로 아래로 내려가며 스왑해나간다.

루트 노드 _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 같은 기본 데이터 타입이 아닌 사용자 정의 객체 타입이라면 비교할 기준을 따로 마련해 주어야 우선순위 큐에 넣을 수 있다. (우선 순위 큐 자체가 비교와 비교를 거듭하여 항상 부모 > 자식 관계를 유지하게 하는 자료구조이기 때문)

'공부 > 인프런 - Rookiss' 카테고리의 다른 글

Part 3. 유니티 엔진 (0)	2023.08.10
Part 2-6-1. A* 길찾기 알고리즘 (0)	2023.08.10
Part 2-5-1. 트리 : 트리 이론과 구현 (0)	2023.08.10
Part 2-4-5. 그래프 : 다익스트라 최단 경로 알고리즘 (0)	2023.08.09
Part 2-4-4. 그래프 : BFS(너비 우선 탐색) (0)	2023.08.09

현재글Part 2-5-2. 트리 : 힙 트리, 우선순위 큐

셩잇님의 잡동사니