自定义堆二叉树实现——随机节点删除

Question

我一直在尝试解决 this 问题。如果将问题陈述与堆二叉树的 ADT 定义进行比较，则它有点像自定义堆二叉树。在堆二叉树中，你总是 deleteMax/deletetMin 取决于堆树的种类，但在这里他们希望你在这个问题中删除一个特定的节点。

好吧，我的解决方案只有一个测试用例失败，当我删除一个叶节点值时会发生这种情况：

这是我在编写堆 class 时所做的努力。尽管源代码很大，但您可能希望关注我遇到问题的 DeleteSpecificValueFromHeap 方法。

我已经使用数组实现了堆二叉树（C# 中的列表由数组支持）。考虑数组中堆二叉树的当前状态：

-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;
            }
        }

    }

更新:

我根据@Raudel 的建议更改了我的 DeleteSpecificValueFromHeap 方法，之后我在 post 中提到的测试用例现在可以了，但是 [=39 上的测试用例 #9 =] 仍然失败。对于无法提供输入案例，我真的很抱歉，因为它有 10 万个输入，不可能放在这里。我现在需要一个鹰眼谁可以干运行我的代码，如果还有什么问题可以帮助我？

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;
            }
        }

Answer 1

问题是，当您在除最后一个位置之外的任何位置删除时，右侧的所有元素都会向左移动一个位置，这可能最终会在堆中停止成为堆。从下面的 3 个步骤开始，您正在执行前两个步骤，但您没有正确执行第 3 个步骤。

1, Delete the value from the array but do not remove it (this creates a "hole" and the tree is no longer "complete") 

2. Replace the deleted value with the "fartest right node" on the lowest level of the heap.
//you can see the first two steps like a swap

3. Heapify (fix the heap)://but you have two possible cases now

     if ( newValue < its parent node )
        Do an UPHeap
     else
        Do a DownHeap

在第 3 步中，您与 parent 进行比较，这会告诉您该怎么做，向上或向下。为此，我建议您分别为UpHeap和DownHeap创建方法，因为您将不止一次地使用它们并且代码会变得更加清晰。

我还应该指出，您正在通过循环查找值，这使得每次删除操作都为 O(n)。正如您在问题陈述中所见，他们最多可以问您 1e5 个问题。根据数组的大小，这可能会给你超出时间限制（TLE）。作为经验法则，对于几乎所有在线裁判来说，解决问题的预期时间都在 1 秒左右。因此，对于大小为 1e5 的数组，您将不得不等待比让您认为应该有更好的东西的时间更长的时间，这是真的。

关键是您可以跟踪值在堆中的位置。您可以将其保存在 HashTable<int, int> 中（例如），这样您就可以请求给定值来获取堆内的位置。通过这种方式，您可以避免循环以获取堆内的位置，但每次在堆内移动该值时都必须更新它。为了更新它，你必须在 UpHeap 和 DownHeap 方法中添加几行，每次你移动一个值 UP/DOWN 堆你更新 HashTable 中交换元素的位置。

更新

我拿了你的代码并做了一些改动，然后我上网并接受了这个问题，现在你可以确定它是有效的。我认为错误在 DownHeap 方法中，这是我真正改变的唯一方法。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ContestLibrary
{
    public class Heap
    {
        List<int> items;

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

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

        public int GetMin()
        {
            if(items.Count == 0)
                throw new Exception("Empty Heap");
            return items[0];
        }

        public void Insert(int item)
        {
            items.Add(item);
            PercolateUpTheNode(items.Count - 1);
        }

        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);

                    if (i == items.Count)
                        return;//cause you deleted the right most node

                    var parentNodeValue = items[(i - 1) / 2];

                    if (items[i] < parentNodeValue)
                        PercolateUpTheNode(i);
                    else
                        PercolateDownTheNode(i);

                    return;
                }
            }
        }

        private void PercolateDownTheNode(int i)
        {
            while (i < items.Count / 2) {
                //get the min child first
                int minChildIndex = 2 * i + 1;
                if (minChildIndex < items.Count - 1 && items[minChildIndex] > items[minChildIndex + 1]) {
                    minChildIndex++;
                }

                if (items[i] <= items[minChildIndex])
                    return;//I'm smaller than the minimum of my children

                //swap
                int temp = items[i];
                items[i] = items[minChildIndex];
                items[minChildIndex] = temp;

                i = minChildIndex;
            }
        }

        private int ParentIndex(int i)
        {
            return (i - 1) / 2;
        }

        private void PercolateUpTheNode(int i)
        {
            while (i > 0)
            {
                var parentValue = items[ParentIndex(i)];
                var currentValue = items[i];

                if (currentValue < parentValue)//swap
                {
                    items[ParentIndex(i)] = currentValue;
                    items[i] = parentValue;
                    i = ParentIndex(i);
                }
                else
                    return;
            }
        }
    }

    public class Problem
    {

        static void Main(string[] args)
        {
            Heap heap = new Heap();
            int q = int.Parse(Console.ReadLine());
            while (q-->0)
            {
                var line = Console.ReadLine().Split();
                int type = int.Parse(line[0]);
                switch (type)
                {
                        case 1:
                            heap.Insert(int.Parse(line[1]));
                        break;
                        case 2:
                            heap.DeleteSpecificValueFromHeap(int.Parse(line[1]));
                        break;
                        default:
                            Console.WriteLine(heap.GetMin());
                        break;
                }
            }
        }
    }
}

自定义堆二叉树实现——随机节点删除

Custom heap binary tree implementation - Random node deletion

c#

algorithm

heap

tree

binary-heap