[C#] 완전 이진트리 1차원배열

정 이진트리 

레벨마다 2배씩 늘어남.

전체 노드의 수는 2^(n+1) - 1

 

 

 

레벨별로 직렬화해 배열에 담으면 아래와 같이 계산됨

루트 = 0

Parent = (인덱스-1)/2;

Child left = (2*인덱스) + 1

Child right = (2*인덱스) + 2

 

---

 

 

using System;
using System.Collections;

public class Heap<T> where T : IHeapItem<T> {
	T[] items;
    int currentItemCount;
    
    public Heap( int maxHeapSize ) 
	{
		items = new T[maxHeapSize];
	}
	
    public int Count {
		get {
			return currentItemCount;
		}
	}

	public bool Contains( T item) 
	{
		return Equals( items[item.HeapIndex], item);
	}
	
    public void UpdateItem( T item )
	{
		SortUp(item);
	}

	// 노드 추가
	public void Add( T item )
	{
		item.HeapIndex = currentItemCount;
		items[currentItemCount] = item;
		SortUp( item );
		currentItemCount ++;
	}

	// 루트 노드 꺼내기
	// 전체를 재구성해야 하므로, 가장 마지막 아이템을 루트로 옮기고 정렬
	public T RemoveFirst()
	{
		T firstItem = items[0];
		currentItemCount--;
		items[0] = items[currentItemCount];
		items[0].HeapIndex = 0;
		SortDown( items[0] );
		return firstItem;
	}

	void SortDown( T item)
	{
		while(true)
		{
			int childIndexLeft = item.HeapIndex * 2 + 1;
			int childIndexRight = item.HeapIndex * 2 + 2;
			int swapIndex = 0;

			// 자식 노드 중에 작은 값을 가진 인덱스 얻기
			if( childIndexLeft < currentItemCount ) 
			{
				swapIndex = childIndexLeft;

				if( childIndexRight < currentItemCount )
				{
					if( items[childIndexLeft].CompareTo(items[childIndexRight]) > 0 )
					{
						swapIndex = childIndexRight;
					}
				}

				// 현재 노드보다 자식 노드값이 작은경우 부모와 자식 위치 변경
				if( item.CompareTo( items[swapIndex]) > 0 )
				{
					Swap( item, items[swapIndex]);
				} else {
					return;
				}
			} else {
				return;
			}
		}
	}


	// 해당 인덱스의 부모와 비교해 작은 값을 부모로 변경
	void SortUp(T item) 
	{
		int parentIndex = (item.HeapIndex-1)/2;

		// 부모와 계속 비교 하면서 부모보다 값이 작은 경우 교체
		while(true)
		{
			T parentItem = items[parentIndex];
			if( item.CompareTo(parentItem) < 0 )
			{
				Swap( item, parentItem );
			} else {
				break;
			}
		}
	}

	void Swap( T itemA, T itemB )
	{
		items[itemA.HeapIndex] = itemB;
		items[itemB.HeapIndex] = itemA;
		int itemAIndex = itemA.HeapIndex;
		itemA.HeapIndex = itemB.HeapIndex;
		itemB.HeapIndex = itemAIndex;
	}
}


public interface IHeapItem<T> : IComparable<T>
{
	int HeapIndex {
		get;
		set;
	}
}

public class Node : IHeapItem<Node>
{
	int value;
	int heapIndex;

	public int HeapIndex
	{   
		get {
			return heapIndex;
		}

		set {
			heapIndex = value;
		}
	}

	public int CompareTo( Node nodeToCompare)
	{
		int compare = value.CompareTo( nodeToCompare.value );
		return compare;
	}
}