Блог

Я пытаюсь написать свою собственную очередь приоритетов с минимальной сортировкой кучи, но я не получаю правильный вывод.

Мои входные данные — это 8 элементов с разными приоритетами:

 [0] : 14
[1] : 5
[2] : 10
[3] : 9
[4] : 6
[5] : 3
[6] : 1
[7] : 2
  

Очевидно, что выходные данные должны отображать эти приоритеты в порядке (от наименьшего к наибольшему), но получается так:

 [0] => Priority 1
[1] => Priority 14
[2] => Priority 5
[3] => Priority 10
[4] => Priority 9
[5] => Priority 6
[6] => Priority 3
[7] => Priority 2
  

По крайней мере, первый элемент правильный, но после этого все неверно.

Вот как я добавляю свои данные:

     public void Add(T item)
    {
        _data.Add(item); // add to end of list

        SortUp(); // bubble the element up the heap
    }
    private void SortUp()
    {
        // the last element we just added
        int itemIndex = _data.Count - 1;
        while (true)
        {
            int parentIndex = (itemIndex - 1) / 2;

            //the lower the priority number, the higher the priority
            if (_data[itemIndex].Priority < _data[parentIndex].Priority)
            {
                //swap with parent
                T temp = _data[parentIndex];
                _data[parentIndex] = _data[itemIndex];
                _data[itemIndex] = temp;
                
                // update item index to parent index for next loop
                itemIndex = parentIndex;
            }
            else
            {
                break;
            }
         }
     }
  

Затем я пытаюсь удалить элементы из очереди, и именно здесь порядок получается неправильным в зависимости от приоритетов:

     public T Pop()
    {
        item = _data[0];

        //get the last element and set it to front of queue
        int lastIndex = Count - 1;
        _data[0] = _data[lastIndex];
        _data.RemoveAt(lastIndex);

        SortDown();

        return item;
    }
    private void SortDown()
    {
        // item we are sorting is at front of the queue
        int itemIndex = 0;
        while (true)
        {
            int leftChildIndex = 2 * itemIndex   1;
            int rightChildIndex = 2 * itemIndex   2;

            // check if priority is higher than left child node
            if (leftChildIndex < Count amp;amp; _data[itemIndex].Priority < _data[leftChildIndex].Priority)
            {
                int swapIndex;
                // check if priority is also higher than right child node
                if (rightChildIndex < Count amp;amp; _data[itemIndex].Priority <_data[rightChildIndex].Priority) 
                {
                    swapIndex = rightChildIndex;
                }
                else
                {
                    swapIndex = leftChildIndex;
                }

                //swap with child swapIndex
                T temp = _data[swapIndex];
                _data[swapIndex] = _data[itemIndex];
                _data[itemIndex] = temp;
                
                //update itemIndex to swapIndex for next loop
                itemIndex = swapIndex;
            }
            else
            {
                break;
            }
        }
    }
  

Кто-нибудь знает, где моя логика отключена, кажется, я не вижу, что я сделал не так.

 public T Deque()
{
    T retval = _data[0];
    _data[0] = _data[Count - 1];
    _data.RemoveAt(Count - 1);
    int cnt = 0;
    while(cnt < Count - 1)
    {
        int lcmp = 0, rcmp = 0;
        if(cnt * 2   1 < Count)
        {
            lcmp = _data[cnt].CompareTo(_data[cnt * 2   1]);
        }
        if(cnt * 2   2 < Count)
        {
            rcmp = _data[cnt].CompareTo(_data[cnt * 2   2]);
        }
        int target = -1;
        if(lcmp == -1 amp;amp; rcmp == -1)
        {
            if(_data[cnt * 2   1].CompareTo(_data[cnt * 2   2]) != -1)
            {
                target = cnt * 2   1;
            }
            else
            {
                target = cnt * 2   2;
            }
        }
        else if(lcmp == -1)
        {
            target = cnt * 2   1;
        }
        else if(rcmp == -1)
        {
            target = cnt * 2   2;
        }
        else
        {
            break;
        }
        T temp = _data[cnt];
        _data[cnt] = _data[target];
        _data[target] = temp;
        cnt = target;
    }
    return retval;
}
  

Получите результат сравнения обоих дочерних элементов, и если обе стороны допустимы для замены, выберите элемент с более низким приоритетом.