C# 힙 트리(Heap tree) 구현

힙 트리(Heap tree) 구현

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.

 

힙 트리(Heap)의 종류

• 최대 힙(max heap)
  
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • key(부모 노드) >= key(자식 노드)
• 최소 힘(min heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  • key(부모 노드) >= key(자식 노드)

최대 힙과 최소 힙

 

힙 트리(Heap tree)의 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용하지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. 
  • 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
• 힙에서의 부모 노드와 자식 노드의 관계
  • 왼쪽 자식의 인덱스 = (부모 노드의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모 노드의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식 노드의 인덱스) / 2

 

 

힙 트리(Heap tree)의 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드와 비교해서 힙의 성질을 만족시킨다.

 

힙 트리(Heap tree)의 삭제

1. 최대 힙에서 최댓값은 루투 노드이므로 루트 노드가 삭제된다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 힙을 재구성한다.

 

예제 코드

using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int[] array = new int[100];

        AddHeap(array, 9);
        AddHeap(array, 7);
        AddHeap(array, 6);
        AddHeap(array, 5);
        AddHeap(array, 4);
        AddHeap(array, 3);
        AddHeap(array, 2);
        AddHeap(array, 2);
        AddHeap(array, 1);
        AddHeap(array, 3);
        RemoveHeap(array);
    }

    static void AddHeap(int[] array, int num)
    {
        if (array[1] == 0)
        {
            array[1] = num;
            return;
        }

        for (int i = 1; i < array.Count(); i++)
        {
            if (array[i] == 0)
            {
                array[i] = num;

                var temp = i;
                while(temp > 1)
                {
                    if (array[temp / 2] < array[temp])
                    {
                        Swap(array, temp / 2, temp);
                    }

                    temp /= 2;
                }

                break;
            }
        }
    }

    static void RemoveHeap(int[] array)
    {
        array[1] = 0;

        for (int i = 2; i < array.Count(); i++)
        {
            if (array[i] == 0)
            {
                Swap(array, 1, i - 1);

                var temp = 1;
                while (true)
                {
                    if (array[temp * 2] > array[temp * 2 + 1])
                    {
                        if (array[temp] < array[temp * 2])
                        {
                            Swap(array, temp, temp * 2);
                            temp *= 2;
                            continue;
                        }
                    }
                    else
                    {
                        if (array[temp] < array[temp * 2 + 1])
                        {
                            Swap(array, temp, temp * 2 + 1);
                            temp = temp * 2 + 1;
                            continue;
                        }
                    }

                    break;
                }

                break;
            }
        }
    }

    static void Swap(int[] array, int src, int dest)
    {
        int temp = array[src];
        array[src] = array[dest];
        array[dest] = temp;
    }
}

참조 사이트

[자료구조] 힙(heap)이란 - Heee's Development Blog

우선순위 큐 Priority Queue