我一直在努力解决 this问题。如果将问题陈述与堆二叉树的 ADT 定义进行比较，则它有点像自定义堆二叉树。在堆二叉树中，您总是根据堆树的类型执行 deleteMax/deletetMin，但在这个问题中，他们希望您删除特定节点。
好吧，我的解决方案只失败了一个测试用例，当我删除一个叶节点值时发生:
这是迄今为止我在编写堆类时所做的努力。尽管源代码很大，但您可能希望关注我遇到问题的 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 方法，之后我在帖子中提到的测试用例现在可以了，但链接上的测试用例 #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;
}
}
最佳答案
问题是当你在除最后一个以外的任何位置移除时，右边的所有元素都会向左移动一个位置，这可能最终会在堆中停止成为堆。 从下面的 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 步中，您与父级进行比较，这会告诉您该怎么做，向上或向下。为此，我建议您分别为 UpHeap 和 DownHeap 创建方法，因为您将不止一次地使用它们并且代码会变得更加清晰。
我还应该指出，您正在通过循环查找值，这使得每次删除操作都为 O(n)。正如您在问题陈述中所见，他们最多可以问您 1e5 个问题。根据数组的大小，这可能会给你超出时间限制(TLE)。作为经验法则，对于几乎所有在线裁判来说，解决问题的预期时间都在 1 秒左右。因此，对于大小为 1e5 的数组，您将不得不等待更长的时间，这让您认为应该有更好的东西，这是真的。
关键是您可以跟踪值在堆中的位置。您可以将其保存在 HashTable<int, int> 中(例如)所以你可以要求一个给定的值来获得堆内的位置。通过这种方式，您可以避免循环以获取堆内的位置，但每次在堆内移动该值时都必须更新它。为了更新它，您必须在 UpHeap 和 DownHeap 方法中添加几行代码，并且每次在堆中向上/向下移动一个值时，您都会更新 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;
}
}
}
}
}
关于c# - 自定义堆二叉树实现——随机节点删除，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48143810/