Heap :: Simpleの要素をPerlで削除する方法

Question

Heap::Simpleモジュールを使用してヒープから特定の要素を削除する方法はありますか？一番上の要素を削除する方法があります。

Answer 1

ヒープの先頭以外のものを削除する場合は、ヒープ構造は必要ありません。データグラフなどで作業している場合は通常、ヒープのみが必要です。あなたはどんな問題に取り組んでいますか？そして、単純なハッシュでは、あなたが望むことはしませんか？

Answer 2

残念ながら、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; 

より洗練されたヒープタイプは、要素の削除をより適切に処理します。 Fibonacci heapsに効率的な削除操作があります。 Binomial heapsは、効率的に他のヒープをマージすることができます。より洗練されたCPANのヒープの実装がいくつかありますが、最適化を深めすぎる前にプロファイルする必要があります。

一般的なアルゴリズムやバイナリヒープから任意のノードを削除することは、バイナリヒープはバイナリツリーの特別なケースであるため、バイナリツリーから削除することと大きく異なりません。

1. ルートから始めて、問題のノードを検索するツリーを歩きます。
2. そのノードを自身のヒープのルートとして扱い、通常どおりに削除します。

両方ともO（logn）操作であり、非常に効率的です。