Как удалить элемент из Heap :: Simple в Perl

Question

Есть ли способ удалить определенный элемент из кучи с помощью модуля Heap :: Simple ? Существует только метод удаления верхнего элемента.

Answer 1

К сожалению, Heap :: Simple не поддерживает извлечение чего-либо, кроме верхнего узла.Вы должны удалить все, вплоть до того, который хотите удалить, а затем положить все остальное обратно.

#!/usr/bin/env perl

use v5.10.0;
use strict;
use warnings;

use Heap::Simple;

my $heap = Heap::Simple->new;

$heap->insert(1,2,3,4,5);

# Remove 1, 2 and 3
my $item_to_remove = 3;
my @items = $heap->extract_upto($item_to_remove);
pop @items;

# Put 1 and 2 back    
$heap->insert(@items);

# 1, 2, 4, 5
say join ", ", $heap->keys;

Более сложные типы кучи лучше справляются с удалением элементов. Кучи Фибоначчи имеют эффективную операцию удаления. Биномиальные кучи может эффективно объединять другие кучи, что ускоряет процесс "вставки их назад".Есть несколько реализаций более сложных куч в CPAN, но вам следует профилировать, прежде чем вы слишком углубитесь в оптимизацию.

Общий алгоритм или удаление произвольного узла из двоичной кучи мало чем отличается от удаления его избинарное дерево, поскольку бинарные кучи - это просто особый случай бинарного дерева.

1. Начиная с корня, идите по дереву в поисках рассматриваемого узла.узел в качестве корня своей собственной кучи и обычно удаляет его.

Оба являются операциями O (logn) и довольно эффективны.

Answer 2

Если вы хотите удалить что-либо, кроме вершины кучи, тогда вам не нужна структура кучи. Обычно вам нужна куча, только если вы работаете с графиками данных или чем-то подобным. Над какой проблемой вы работаете? И разве простой хеш не сделает то, что вы хотите?