Реализация пользовательского двоичного дерева кучи — случайное удаление узла

Я пытался решить этот вопрос. Постановка задачи немного похожа на настроенное двоичное дерево кучи, если сравнить его с определением двоичного дерева кучи в ADT. В двоичном дереве кучи вы всегда делаете deleteMax/deletetMin в зависимости от типа дерева кучи, но здесь они хотят, чтобы вы вместо этого удалили конкретный узел в этой проблеме.

Что ж, мое решение не работает только в одном тестовом случае, когда я удаляю значение, которое является конечным узлом:

Вот усилия, которые я приложил до сих пор при написании класса Heap. Хотя исходный код большой, вы можете сосредоточиться на методе DeleteSpecificValueFromHeap, где я столкнулся с проблемой.

Я реализовал двоичное дерево кучи, используя массив (список в С# поддерживается массивами). Рассмотрим текущее состояние двоичного дерева кучи в массиве:

-1 12 5 13 20 6 7

Бинарное дерево кучи выглядит примерно так:

        -1
    /        \
   12         5
  /   \     /    \
13    20    6     7

Теперь я хочу удалить узел со значением 13. Этот случай не работает в моем двоичном дереве кучи. Можете ли вы указать, как это исправить? Метод DeleteSpecificValueFromHeap - это тот, который в настоящее время борется.

public class Heap
{
    List<int> items;

    public int Root
    {
        get { return items[0]; }
    }

    public Heap()
    {
        items = new List<int>();
    }

    public void Insert(int item)
    {
        items.Add(item);

        if (items.Count <= 1)
            return;

        var i = items.Count - 1;

        while (i > 0)
        {
            var parentNodeValue = items[(i - 1) / 2];
            var newNodeValue = items[i];

            if (newNodeValue < parentNodeValue)
            {
                //we need to percolate up this node. so swap it with parent.
                items[(i - 1) / 2] = newNodeValue;
                items[i] = parentNodeValue;
                //update the position of newly inserted node after swapping
                i = (i - 1) / 2;
            }
            else
                break;
        }
    }

    public void DeleteSpecificValueFromHeap(int val)
    {
        for (var i = 0; i < items.Count; i++)
        {
            if (items[i] == val)
            {
                items[i] = items[items.Count - 1];
                items.RemoveAt(items.Count - 1);
                //reheapify : percolate down this node ith position

                var leftChildIndex = (i * 2) + 1;
                var rightChildIndex = (i * 2) + 2;



                while (leftChildIndex <= items.Count - 1) //chilren are there in the array.
                {
                    //child nodes of node at ith position
                    var child1Value = items[leftChildIndex];

                    if (rightChildIndex <= items.Count - 1)
                    {
                        var child2Value = items[rightChildIndex];
                        var currentNodeValue = items[i];
                        if (child1Value < child2Value)
                        {
                            //swap ith node with child 1
                            items[i] = child1Value;
                            items[leftChildIndex] = currentNodeValue;
                            i = leftChildIndex;
                        }
                        else
                        {
                            items[i] = child2Value;
                            items[rightChildIndex] = currentNodeValue;
                            i = rightChildIndex;
                        }
                    }
                    else
                    {
                        //case of only one child
                        var currentNodeValue = items[i];
                        items[i] = child1Value;
                        items[leftChildIndex] = currentNodeValue;
                        i = leftChildIndex;
                    }
                    leftChildIndex = (i * 2) + 1;
                    rightChildIndex = (i * 2) + 2;
                }
                break;
            }
        }

    }

Обновление:

Я изменил свой метод DeleteSpecificValueFromHeap, как показано ниже, в соответствии с рекомендацией @Raudel, после чего тестовый пример, который я упомянул в посте, теперь в порядке, но тестовый пример № 9 по ссылке все еще не работает. Мне очень жаль, что я не могу предоставить входные данные, поскольку у него есть 0,1 миллиона входных данных, которые невозможно разместить здесь. Теперь мне нужен орлиный глаз, который может запустить мой код в пробном режиме и помочь мне, если все еще что-то не так?

public void DeleteSpecificValueFromHeap(int val)
        {
            for (var i = 0; i < items.Count; i++)
            {
                if (items[i] == val)
                {
                    items[i] = items[items.Count - 1];

                    if (i == items.Count - 1)
                    {
                        //you are deleting the right most leaf node at the lowest level
                        //so nothing needs to be done apart from deleting the node.
                        items.RemoveAt(items.Count - 1);
                        break;
                    }

                    items.RemoveAt(items.Count - 1);

                    if (i == 0)
                        //it is the root node. The only option is to percolate down.
                        PercolateDownTheNode(i);
                    else
                    {
                        var parentNodeValue = items[(i - 1) / 2];
                        if (items[i] < parentNodeValue)
                            PercolateUpTheNode(i);
                        else
                            PercolateDownTheNode(i);
                    }

                    break;
                }
            }

        }

        private void PercolateDownTheNode(int i)
        {
            //reheapify : percolate down this node ith position
            var leftChildIndex = (i * 2) + 1;
            var rightChildIndex = (i * 2) + 2;

            while (leftChildIndex <= items.Count - 1) //chilren are there in the array.
            {
                //child nodes of node at ith position
                var child1Value = items[leftChildIndex];

                if (rightChildIndex <= items.Count - 1)
                {
                    var child2Value = items[rightChildIndex];
                    var currentNodeValue = items[i];
                    if (child1Value < child2Value)
                    {
                        //swap ith node with child 1
                        items[i] = child1Value;
                        items[leftChildIndex] = currentNodeValue;
                        i = leftChildIndex;
                    }
                    else
                    {
                        items[i] = child2Value;
                        items[rightChildIndex] = currentNodeValue;
                        i = rightChildIndex;
                    }
                }
                else
                {
                    //case of only one child
                    var currentNodeValue = items[i];
                    items[i] = child1Value;
                    items[leftChildIndex] = currentNodeValue;
                    i = leftChildIndex;
                }
                leftChildIndex = (i * 2) + 1;
                rightChildIndex = (i * 2) + 2;
            }
        }

        private void PercolateUpTheNode(int i)
        {
            while (i > 0)
            {
                var parentNodeValue = items[(i - 1) / 2];
                var newNodeValue = items[i];

                if (newNodeValue < parentNodeValue)
                {
                    //we need to percolate up this node. so swap it with parent.
                    items[(i - 1) / 2] = newNodeValue;
                    items[i] = parentNodeValue;
                    //update the position of newly inserted node after swapping
                    i = (i - 1) / 2;
                }
                else
                    break;
            }
        }