[C#] 힙 (Heap)

1. 힙이란?

: 완전 이진 트리(Complete Binary Tree)의 일종. 여러 값의 데이터들 중 최대값과 최소값을 빠르게 찾아낼 수 있는 자료구조입니다. (시간복잡도로 따지면 O(logn)이 걸림)

 

* 힙의 특징

- 중복 값을 허용

- 루트가 최대값(새로운 데이터가 추가될 때 부모노드와 크기를 비교해 크기가 더 큰 값을 부모노드로 올리기 때문)

- 새로운 데이터를 추가할 때 작은 레벨 순서대로 채움(왼쪽부터)

2. 이진 탐색 트리와 힙의 차이

* 공통점 : 둘 다 이진 트리.

* 차이점

- 힙은 이진 탐색 트리와 달리 중복 값을 허용.

- 힙은 각 노드들이 부모노드의 데이터 값보다 작거나 같음.

- 이진 탐색 트리는 말 그대로 탐색을 위한 자료구조이고, 힙은 최대값과 최소값 검색을 위한 자료구조.

3. 힙의 구현(삽입과 삭제)

1) 삽입

* 힙은 아래와 같이 인덱스 번호를 구하기 편하게 하기 위해 루트의 인덱스 번호를 1로 지정하기도 합니다.

- 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2

  오른족 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1

public bool addHeap(int data)
{
    if (heapList.Count == 0)
    {
        heapList = new List<int?>();
        heapList.Add(0); //0번 인덱스는 사용하지 않음(계산하기 편하게 하기 위해)
        heapList.Add(data); //1번 인덱스부터 데이터를 넣음.
    }
    else
    {
        heapList.Add(data);
        int parent_i, insert_i  = heapList.Count - 1; //추가
        while (is_up(insert_i)) //insert_i를 부모노드와 크기 비교
        {
            parent_i = insert_i / 2;
            swap(heapList, insert_i, parent_i); //두 데이터 위치를 바꿈
            insert_i = parent_i;
        }
    }
    return true;
}

public bool is_up(int insert_i)
{
    if (insert_i <= 1) return false; //루트일 경우 변경 x
    if (minHeap[insert_i / 2].weight > minHeap[insert_i].weight) return true;
    else return false;
}

 

2) 삭제

* 보통 최상단의 노드(= 루트)를 삭제하고, 그 밑의 자식 노드들의 크기를 비교해 더 큰 수를 위로 올리는 작업을 반복함.

public int? heapOut()
{
    if (heapList.Count == 0) return null;
    int? outData = (int)heapList[1]; //최대값을 가져옴
    heapList[1] = heapList[heapList.Count - 1]; //마지막 값을 가져옴
    heapList.RemoveAt(heapList.Count - 1);
    int idx = 1;
    int i_left, i_right;
    while (is_down(idx))
    {
        i_left = idx * 2;
        i_right = idx * 2 + 1;
        if (i_right >= heapList.Count && heapList[idx] < heapList[i_left])
        {
            swap(heapList, idx, i_left);
            idx = i_left;
        }
        else if (i_right < heapList.Count)
        {
            if (heapList[i_left] > heapList[i_right])
            {
                swap(heapList, idx, i_left);
                idx = i_left;
            }
            else
            {
                swap(heapList, idx, i_right);
                idx = i_right;
            }
        }
    }
    return outData;
}

public bool is_down(int insert_i)
{
    int i_left = insert_i * 2;
    int i_right = insert_i * 2 + 1;
    if (i_left > heapList.Count) //자식 노드가 없을 때
        return false;
    else if (i_left == heapList.Count)//자식 노드가 하나만 있을 때
    {
        if (heapList[insert_i] < heapList[i_left])
            swap(heapList, i_left, insert_i);
        return false;
    }
    else //자식 노드가 두개 있을 때
    {
        if (heapList[i_right] > heapList[i_left] && heapList[insert_i] < heapList[i_right]) return true;
        else if (heapList[i_right] <= heapList[i_left] && heapList[insert_i] < heapList[i_left]) return true;
        else return false;
    }
}

 

[C# 기초] #21. 힙(Heap) (tistory.com)