게임알고리즘 10주차 - Heap

Heap

Dictionary meaing

Heap : 쌓아놓은 더미, 가장 위에 놓인 것이 우선순위가 높다.

 

Heap property

어떤 마디에 저장된 값은 그 마디의 자식 마디에 저장된 값보다 크거나 같다. (max heap)

반대의 경우 min heap이다.

 

Heap Structure

- 힙의 성질을 만족하는 실질적인 완전 이진트리

- 검색 시간이 logN을 보장한다.

- Heap은 최대값 또는 최소값을 빠르게 찾을 수 있도록 고안된 완전이진트리구조. (Priority Queue를 구현하는데 적합)

- sorting 비용이 저렴하다는 장점이 있다.

- 우선순위에 해당하는 데이터만 관리 해 주는 자료구조.

 

힙의 조건

- 빈 트리이거나

- 루트의 키가 왼쪽과 오른쪽 자식의 키보다 크거나 같다.

- 왼쪽과 오른쪽 자식 사이에는 키의 크기와 상관없다.

- 서브트리는 힙의 조건을 만족해야 한다.

 

힙의 표현

- 배열로 표시하는 것이 가장 효율적이다.

- 루트부터 시작해서 위에서 아래쪽으로, 왼쪽에서 오른쪽으로 진행한다.

- 노트필기하는 순서로 트리를 순회하면서 인덱스를 부여한다.

- 루트노드 배열 인덱스 : 0

 

배열 인덱스 연산

- 인덱스 K의 왼쪽 자식 노드 : 2K+1

- 인덱스 K의 오른쪽 자식 노드 : 2K+2

- 인덱스 K의 부모 노드 : (K-1)/2

 

Heap의 구현

Remove root node from Heap

우선순위가 가장 큰 루트 노드 삭제

- 루트 노드를 직접 삭제하면 이후 힙을 재구성하는 것이 복잡하다.

- 배열의 마지막 요소를 루트 노드 위치로 복사하여 Down Heap 진행한다.

 

Down Heap

- Heap Rebuilding 과정

- 루트 노드로부터 시작해서 제자리를 찾기까지 굴러 떨어진다.

- 왼쪽 자식과 오른쪽 자식을 모두 비교하여 가장 큰 것과 현재 키 값을 swapping한다.

Remove(Items[])
{
    retVal = Items[0]
    Items[0] = Items[Count-1]
    
    Count--
    HeapifyDown(Items[ ], 0)
    
    return retVal;
}

HeapifyDown(Items[], Current)
{
    if (Current == Leaf)
    {
    	do nothing;
    }
    else
    {
        Child = 2 * Current + 1
        
        if (Currrent has RChild)
        {
            RChild = Child + 1
            
            if (Items[RChild] > Items[Child])
            {
	            Child = RChild;
            }
        }
        if (Items[Current] < Items[Child])
        {
            Swap Items[Current] and Items[Child]
            HeapifyDown(Items, Child)
        }
    }
}

 

Efficiency of remove

- 배열의 마지막 레코드를 처음으로 복사 : 1

- 루트노드를 제자리를 찾기까지 굴러 떨어짐

   최악의 경우 리프까지 굴러 떨어짐 - 비교 횟수 : 2logN

   Swapping에 의한 복사 : 3logN (Swapping : T=A, A=B, B=T)

- 전체 : 1+2logN + 3logN = 5logN + 1 ≅ 0(logN)

 

Add a node to Heap

Add algorithm

- 추가할 레코드를 배열의 마지막 위치에 추가

- 추가한 레코드가 제자리를 찾기까지 위로 올림 (Up Heap)

Add(Items[], Data)
{
    Items[Count] = Data;
    Current = Count;
    Parent = (Current - 1) / 2;

    while((Current != 0) && (Items[Current] > Items[Parent]))
    {
        Swap Items[Current] with Items[Parent];
        Current = Parent;
        Parent = (Current - 1) / 2;
    }
    Count++;
}

 

Heap VS Vinary Search Tree

- 힙은 완전이진트리를 보장 (균형트리)

- 최악의 경우 트리의 높이

  힙 : logN

  이진탐색트리 : N (Skewed Tree, 편향된 이진트리)

- 가장 큰 키값의 탐색 효율

  힙 : 0(1)

  이진탐색트리 : 0(logN)/ 최악의 경우 (Skewed Tree) : 0(N)

구분	Insert	Remove	Retrieve
이진 탐색트리	logN	logN	logN
힙	logN(보장)	logN(보장)	1

 

Heap Building

Idea

1. 𝒏개의 키를 이용하여 힙을 구성한다. (make heap)

2. 루트에 있는 제일 큰 값을 제거하고 힙을 제구성 한다. (remove & down heap)

3. Step 2를 𝒏-1번 반복한다.

 

Make heap 방법

방법 1 : 데이터가 입력되는 순서대로 heap을 매번 구성 (sift-up)

Sift-up Make heap 효율 - 데이터가 삽입될 때마다 대략 log𝒏의 경로를 거쳐 위로 올라감 - 𝒏개가 삽입된다면 𝒏log𝒏의 효율 Remove & Rebuild heap 효율 - 루트를 제거하고 가장 마지막 데이터를 루트로 보사하여 log𝒏 경로를 거쳐 아래로 내려 옴 - 𝒏개에 대해 remove & rebuild 하므로 𝒏log𝒏의 효율 Heap Sort의 효율 𝑶(𝒏log𝒏) + 𝑶(𝒏log𝒏) ≅ 𝑶(𝒏log𝒏)

방법 2 : 모든 데이터를 트리에 넣은 상태에서 heap 구성 (sift-down)

a. The initial structure : 일단 모두 넣은 상태 b. The subtrees, whose roots have depth d-1, are maed into heaps. c. The left subtree, whose root has depth d-2, are made into a heap. d. Depth가 d-3인 노드의 sift-down Sift-down Make heap 효율 - 입력 크기 (총 키의 개수) : n, where n = 2^d 가정 : d를 실질적인 완전이진트리의 깊이라고 하면, d = logN. 이때 d의 깊이를 가진 마디는 정확히 하나이고, 그 마디는 d개의 조상(ancestor)을 가진다. 일단 깊이가 d인 그 마디가 없다고 가정하고 키가 sift 되는 상한값 (upper bound)을 구해 보자.) 총 sift down 횟수 = sum{from j=0 to d-1} 2^j (d - j - 1)  한 번의 sift down에서는 2번의 키 비교가 필요 : 2(𝒏-1) Sift down 효율 = 𝑶(𝒏)

* sift : 체로 걸러내다.