Реализация пользовательского двоичного дерева кучи - случайное удаление узла
Я пытался решить этот вопрос. Задача - это немного настраиваемого двоичного дерева кучи, если сравнить его с определением 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;
}
}
}
Обновление:
Я изменил свой 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;
}
}
1 ответ
Проблема в том, что когда вы удаляете в любой позиции, кроме последней, все элементы вправо смещаются влево на одну позицию, и это может закончиться в куче, чтобы перестать быть кучей. Из 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
На третьем шаге вы сравниваете себя с родителем, и это говорит вам, что делать, подниматься или опускаться. Для этого я рекомендую вам создавать методы для UpHeap и DownHeap отдельно, потому что вы будете использовать их более одного раза, и код станет более понятным.
Я должен также указать, что вы находите значение с помощью цикла, и это делает каждое удаление O(n). Как вы можете видеть в постановке задачи, они могут задать вам до 1е5 вопросов. Это, вероятно, даст вам превышение лимита времени (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;
}
}
}
}
}