jeudi 22 avril 2021

Can someone explain what is this HeapQueue data structure and why designed it

https://learn.unity.com/project/2d-platformer-template

Have been struggling on studying this unity tutorial project. Generally speaking I am confused about the method names that are used here.

Also, I researched the algorithm of sift up and sift down but the code here seems opposed to the normal heap concept. Although there are annotation I can't fully understand this pop method.

    public class HeapQueue<T> where T : IComparable<T> {
    List<T> items;

    public int Count { get { return items.Count; } }

    public bool IsEmpty { get { return items.Count == 0; } }

    public T First { get { return items[0]; } }

    public void Clear() => items.Clear();

    public bool Contains(T item) => items.Contains(item);

    public void Remove(T item) => items.Remove(item);

    public T Peek() => items[0];

    public HeapQueue()
    {
        items = new List<T>();
    }

    public void Push(T item)
    {
        //add item to end of tree to extend the list
        items.Add(item);
        //find correct position for new item.
        SiftDown(0, items.Count - 1);
    }

    public T Pop()
    {

        //if there are more than 1 items, returned item will be first in tree.
        //then, add last item to front of tree, shrink the list
        //and find correct index in tree for first item.
        T item;
        var last = items[items.Count - 1];
        items.RemoveAt(items.Count - 1);
        if (items.Count > 0)
        {
            item = items[0];
            items[0] = last;
            SiftUp();
        }
        else
        {
            item = last;
        }
        return item;
    }


    int Compare(T A, T B) => A.CompareTo(B);

    void SiftDown(int startpos, int pos)
    {
        //preserve the newly added item.
        var newitem = items[pos];
        while (pos > startpos)
        {
            //find parent index in binary tree
            var parentpos = (pos - 1) >> 1;
            var parent = items[parentpos];
            //if new item precedes or equal to parent, pos is new item position.
            if (Compare(parent, newitem) <= 0)
                break;
            //else move parent into pos, then repeat for grand parent.
            items[pos] = parent;
            pos = parentpos;
        }
        items[pos] = newitem;
    }

    void SiftUp()
    {
        var endpos = items.Count;
        var startpos = 0;
        //preserve the inserted item
        var newitem = items[0];
        var childpos = 1;
        var pos = 0;
        //find child position to insert into binary tree
        while (childpos < endpos)
        {
            //get right branch
            var rightpos = childpos + 1;
            //if right branch should precede left branch, move right branch up the tree
            if (rightpos < endpos && Compare(items[rightpos], items[childpos]) <= 0)
                childpos = rightpos;
            //move child up the tree
            items[pos] = items[childpos];
            pos = childpos;
            //move down the tree and repeat.
            childpos = 2 * pos + 1;
        }
        //the child position for the new item.
        items[pos] = newitem;
        SiftDown(startpos, pos);
    }
}

}

This is how the pop method is used on the tick method in another class

enter image description here

Aucun commentaire:

Enregistrer un commentaire