최소힙

Notice

Recent Posts

Recent Comments

Link

« 2026/04 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30

Tags more

Archives

Today

Total

관리 메뉴

낑깡의 게임 프로그래밍 도전기

최소힙 본문

Unity C#

최소힙

낑깡겜플밍 2023. 11. 23. 21:50

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UIElements;

public class CompleteBinaryTree
{
    public List<int> array;
    protected const int rootIndex = 1;

    public CompleteBinaryTree()
    {
        array = new List<int>();
        array.Add(-1);
    }

    public virtual void Add(int value)
    {
        array.Add(value);
    }
    public virtual int Remove()
    {
        int removeValue = array[array.Count - 1];
        array.RemoveAt(array.Count - 1);
        return removeValue;
    }
}

public class MinHeap : CompleteBinaryTree
{
    public override void Add(int value)
    {
        array.Add(value);

        int inputCurIndex = array.Count - 1;
        while(inputCurIndex > 0)
        {
            int curParantIndex = inputCurIndex / 2;
            if (array[inputCurIndex] < array[curParantIndex])
                SwapValue(inputCurIndex, curParantIndex);
            else
                break;

            inputCurIndex = curParantIndex;
        }
    }
    public void SwapValue(int indexA,int indexB)
    {
        int tempValue = array[indexA];
        array[indexA] = array[indexB];
        array[indexB] = tempValue;
    }
    public override int Remove()
    {
        int leastValue = array[rootIndex];

        array[rootIndex] = array[array.Count - 1];
        array.RemoveAt(array.Count - 1);

        int curParentIndex = rootIndex;
        int last = array.Count - 1;

        while(curParentIndex < last)
        {
            int childIndex = curParentIndex * 2;


            if(childIndex < last)
            {
                if (array[childIndex] > array[childIndex +1])
                {
                    childIndex = childIndex + 1;
                }
            }

            if (childIndex > last)
                break;
            if (array[curParentIndex] <= array[childIndex])
                break;

            SwapValue(childIndex, curParentIndex);
            curParentIndex = childIndex;
          
        }

        return leastValue;
    }
}


public class Test : MonoBehaviour
{

    // Start is called before the first frame update
    void Start()
    {
        MinHeap minHeap = new MinHeap();

        minHeap.Add(30);
        minHeap.Add(20);
        minHeap.Add(10);
        minHeap.Add(40);
        minHeap.Add(50);
        minHeap.Add(60);

        Debug.Log(minHeap.Remove());
        Debug.Log(minHeap.Remove());
        Debug.Log(minHeap.Remove());
        Debug.Log(minHeap.Remove());
        Debug.Log(minHeap.Remove());
        Debug.Log(minHeap.Remove());
    }

}

우선순위 큐

우선 순위 큐

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UIElements;


public class CompleteBinaryTree
{
    public List<int> array;
    protected const int rootIndex = 1;

    public CompleteBinaryTree()
    {
        array = new List<int>();
        array.Add(-1);
    }

    public virtual void Add(int value)
    {
        array.Add(value);
    }
    public virtual int Remove()
    {
        int removeValue = array[array.Count - 1];
        array.RemoveAt(array.Count - 1);
        return removeValue;
    }
}

public class MaxHeap : CompleteBinaryTree
{
    public override void Add(int value)
    {
        array.Add(value);

        int inputCurIndex = array.Count - 1;

        while(inputCurIndex > rootIndex)
        {
            int curParantIndex = inputCurIndex / 2;
            if (array[inputCurIndex] > array[curParantIndex])
                SwapValue(inputCurIndex, curParantIndex);
            else
                break;

            inputCurIndex = curParantIndex;
        }
    }
    public override int Remove()
    {
        int leastValue = array[rootIndex];

        array[rootIndex] = array[array.Count - 1];
        array.RemoveAt(array.Count - 1);

        int curParentIndex = rootIndex;
        int last = array.Count - 1;

        while (curParentIndex < last)
        {
            int childIndex = curParentIndex * 2;
            if (childIndex < last)
            {
                if (array[childIndex] < array[childIndex + 1])
                {
                    childIndex = childIndex + 1;
                }
            }

            if (childIndex > last)
                break;
            if (array[curParentIndex] >= array[childIndex])
                break;

            SwapValue(childIndex, curParentIndex);
            curParentIndex = childIndex;

        }

        return leastValue;
    }
    public void SwapValue(int indexA,int indexB)
    {
        int tempValue = array[indexA];
        array[indexA] = array[indexB];
        array[indexB] = tempValue;
    }
    
}

public class PriortyQueueNode
{
    public int key;
    public string data;

    public PriortyQueueNode(int key, string data)
    {
        this.key = key;
        this.data = data;
    }
}

public class PriortyQueue : MaxHeap
{
    Dictionary<int, PriortyQueueNode> nodeDic;

    public PriortyQueue()
    {
        nodeDic = new Dictionary<int, PriortyQueueNode>();
    }
    public void Enqueue(int key,string data)
    {
        nodeDic.Add(key, new PriortyQueueNode(key, data));
        Add(key);
    }
    public string Dequeue()
    {
        return nodeDic[Remove()].data;
    }
}


public class Test : MonoBehaviour
{
    //트리
    //이진트리
    //완전이진트리
    //힙
    //우선순위 큐


    //힙을 사용한 자료구조로서
    //키값과 데이터 두 가지를 가지고,
    //들어갈 때(Enqueue), 키값을 통해 힙내부에서 정렬을 하고,
    //뺄 때(Dequeue), 힙의 루트부분(최대힙이면 가장 큰 키값, 최소힙이면 가장 작은 키값)
    //을 가져와 데이터를 쓴다.

    // Start is called before the first frame update
    void Start()
    {
        PriortyQueue priortyQueue = new PriortyQueue();

        priortyQueue.Enqueue(1, "슬라임");
        priortyQueue.Enqueue(2, "스켈레톤");
        priortyQueue.Enqueue(10, "드래곤");
        priortyQueue.Enqueue(5, "골-든스켈레톤");


        Debug.Log(priortyQueue.Dequeue());
        Debug.Log(priortyQueue.Dequeue());
        Debug.Log(priortyQueue.Dequeue());
        Debug.Log(priortyQueue.Dequeue());

    }

}

public class CompleteBinaryTree
{
    public List<int> array;
    protected const int rootIndex = 1;

    public CompleteBinaryTree()
    {
        array = new List<int>();
        array.Add(-1);
    }

    public virtual void Add(int value)
    {
        array.Add(value);
    }
    public virtual int Remove()
    {
        int removeValue = array[array.Count - 1];
        array.RemoveAt(array.Count - 1);
        return removeValue;
    }
}

public class MaxHeap : CompleteBinaryTree
{
    public override void Add(int value)
    {
        array.Add(value);

        int inputCurIndex = array.Count - 1;

        while(inputCurIndex > rootIndex)
        {
            int curParantIndex = inputCurIndex / 2;
            if (array[inputCurIndex] > array[curParantIndex])
                SwapValue(inputCurIndex, curParantIndex);
            else
                break;

            inputCurIndex = curParantIndex;
        }
    }
    public override int Remove()
    {
        int leastValue = array[rootIndex];

        array[rootIndex] = array[array.Count - 1];
        array.RemoveAt(array.Count - 1);

        int curParentIndex = rootIndex;
        int last = array.Count - 1;

        while (curParentIndex < last)
        {
            int childIndex = curParentIndex * 2;
            if (childIndex < last)
            {
                if (array[childIndex] < array[childIndex + 1])
                {
                    childIndex = childIndex + 1;
                }
            }

            if (childIndex > last)
                break;
            if (array[curParentIndex] >= array[childIndex])
                break;

            SwapValue(childIndex, curParentIndex);
            curParentIndex = childIndex;

        }

        return leastValue;
    }
    public void SwapValue(int indexA,int indexB)
    {
        int tempValue = array[indexA];
        array[indexA] = array[indexB];
        array[indexB] = tempValue;
    }
    
}

public class PriortyQueueNode
{
    public int key;
    public string data;

    public PriortyQueueNode(int key, string data)
    {
        this.key = key;
        this.data = data;
    }
}

public interface IPriortyQueue
{
    void Enqueue(int key, string data);
    string Dequeue();
}

public class AdaptorPriortyQueue : MaxHeap, IPriortyQueue
{
    Dictionary<int, PriortyQueueNode> nodeDic;

    public AdaptorPriortyQueue()
    {
        nodeDic = new Dictionary<int, PriortyQueueNode>();
    }
    public void Enqueue(int key,string data)
    {
        nodeDic.Add(key, new PriortyQueueNode(key, data));
        Add(key);
    }
    public string Dequeue()
    {
        return nodeDic[Remove()].data;
    }
}


public class Test : MonoBehaviour
{
    //트리
    //이진트리
    //완전이진트리
    //힙
    //우선순위 큐

    //힙을 사용한 자료구조로서
    //키값과 데이터 두 가지를 가지고,
    //들어갈 때(Enqueue), 키값을 통해 힙내부에서 정렬을 하고,
    //뺄 때(Dequeue), 힙의 루트부분(최대힙이면 가장 큰 키값, 최소힙이면 가장 작은 키값)
    //을 가져와 데이터를 쓴다.
    void Start()
    {
        AdaptorPriortyQueue adaptorPriortyQueue = new AdaptorPriortyQueue();
        IPriortyQueue priortyQueue = adaptorPriortyQueue;

        priortyQueue.Enqueue(1, "슬라임");
        priortyQueue.Enqueue(2, "스켈레톤");
        priortyQueue.Enqueue(10, "드래곤");
        priortyQueue.Enqueue(5, "골-든스켈레톤");

        Debug.Log(priortyQueue.Dequeue());
        Debug.Log(priortyQueue.Dequeue());
        Debug.Log(priortyQueue.Dequeue());
        Debug.Log(priortyQueue.Dequeue());
    }
}

'Unity C#' 카테고리의 다른 글

Sort 해설 (0)	2023.11.28
Sort 하기 (0)	2023.11.24
유니티 C# Behaviour Tree(행동트리) ...어렵다 (0)	2023.11.22
유니티 C# tree(트리) (0)	2023.11.21
제트카라 재 커스텀 (0)	2023.11.17

'Unity C#' Related Articles

낑깡의 게임 프로그래밍 도전기

최소힙 본문

최소힙

'Unity C#' 카테고리의 다른 글

티스토리툴바