[자료구조] 힙트리와 이진트리 개념 및 우선순위큐 구현 C#

이진트리는 한 노드에 2개의 노드를 가지고 있는 트리로 외쪽으로 갈수록 값이 현재 값보다 작아지며 오른쪽으로 갈수록 현재 값보다 커진다.

 

이진검색트리

이진트리는 점점 직전보다 큰 값을 추가한다면 오른쪽으로 추가만 되기 때문에 오른쪽 왼쪽의 균형이 깨질 수 있다. 그래서 이진 검색 트리는 주기적으로 재배치를 통해 균형을 유지해야한다.(AVL, Red-Black)

 

힙트리

힙트리는 부모노드가 가진 값은 항상 자식 노드가 가진 값보다 크다.

마지막 레벨을 제외한 모든 레벨에 노드가 모두 차있어야 한다.

마지막 레벨에 노드가 있을 떄는 항상 왼쪽부터 순서대로 채워야 한다.

노드 개수를 알면 트리구조는 무조건 확정할 수 있다.

자식 노드 구하는 공식 

• i번 노드 왼쪽 자식 
  • [(2*i) + 1]
• i번 노드 오른쪽 자식
  • [(2*i) + 1]
• i번 노드의 부모
  • [(i - 1) / 2]

 

우선순위큐

힙트리를 응용 하여 우선순위를 갖는 큐를 만들 수 있다.

BIG-O - log2(N)

    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; //[(i - 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; //[(2*i) + 1]
                int right = 2 * now + 2; //[(2*i) + 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)
            {
                Console.WriteLine(q.Pop());
            }
        }
    }