如何從Perl中的Heap :: Simple中移除元素

有沒有辦法使用Heap::Simple模塊從堆中移除特定的元素？只有一種方法可以刪除頂部元素。如何從Perl中的Heap :: Simple中移除元素

2012-02-25 esmeralda2

如果你想刪除除堆頂部之外的任何東西，那麼你不需要堆結構。如果您使用數據圖表或類似的東西，通常只需要一個堆。你在做什麼問題？而不是一個簡單的散列做你想要的？

2012-02-25 23:50:47 Borodin

我不會那麼遠。使用堆的一個好地方是定時器列表，您可以添加將來發生的事件，查看頂層元素以找出何時設置下一個定時器，並在定時器到期時彈出頂層元素。但有時用戶會要求在計時器到期之前取消計時器。 – hobbs 2012-02-26 00:39:25

@hobbs你如何取消該計時器？ – Schwern 2012-02-26 01:14:04

@Schwen：你在維護一個事件隊列嗎？如果你解釋你的申請，它會幫助我們。如果您需要獨立於堆堆訪問堆中的所有項目，則必須使其成爲一堆指向項目數據的指針。刪除一個項目就涉及到只將這個項目標記爲已刪除，這樣當它從堆中拉出時就可以忽略它。 – Borodin 2012-02-26 03:30:09

不幸的是，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上有一些更復雜的堆棧實現，但在進行優化之前，您應該進行配置。

一般算法或從二進制堆中刪除任意節點與從二進制樹中刪除它沒有多大區別，因爲二進制堆只是二叉樹的特例。

從根開始，沿着搜索相關節點的樹走下去。
將該節點視爲自己的堆的根，並將其正常刪除。

兩者都是O（logn）操作並且效率很高。

來源

2012-02-26 01:24:22 Schwern

如何從Perl中的Heap :: Simple中移除元素

回答

相關問題