Moduł Heap
Uniwersytet Gdański - Instytut Matematyki - Zakład Informatyki - Strona domowaSpis treści
Opis
Heap to moduł autorstwa John'a Macdonald'a - perlowe rozszerzenia do przechowywania częściowo posortowanych danych. Moduł ten dostarcza procedur, które zarządzają kopcem elementów. Kopiec jest częściowo posortowaną strukturą, która jest zawsze zdolna do łatwego wyciągnięcia najmniejszego elementu w strukturze (lub największego, gdy mamy odwrócone porównywanie). Jeśli zbiór elementów zmienia się automatycznie, kopiec posiada mniejszą górę, niż trzymanie zbioru całkowicie posortowanego. Elementy kopca muszą być obiektami Heap::Elem oraz wszystkie elementy wstawione do jednego kopca muszą być wzajemnie zgodne - każdy tej samej klasy lub różnych klas nie różniących się w odniesieniu do interfejsu Heap::Elem.
Download
- Pakiet możemy pobrać z CPANu
Instalacja w systemie UNIX'owym
Po rozpakowaniu modułu wydajemy polecenia
perl Makefile.PL
make
make install
Jeżeli wszystko poszło zgodnie z planem, to możemy już korzystać z możliwości naszego nowego modułu. Sprawdzić, czy został pomyślnie zainstalowany możemy, pisząc chociażby takiego jednolinijkowca:
perl -e 'use Heap'
Pomyślne wykonanie programu (żadnych komunikatów) daje nadzieję, że moduł jest zainstalowany i będzie działał.
Dostępne metody
- $heap = HeapClass::new(); - zwraca obiekt nowego kopca
- $heap->DESTROY - przeciwne działania do bless, czyli $heap nie jest już kojarzone z obiektem Heap. Większość normalnych użytkowników modułu Heap nie powinno się przejmować tą metodą, ponieważ DESTROY jest automatycznie wywoływana, kiedy referencja do kopca traci swój zasięg.
- $heap->add($elem) - dodaje nowy element do kopca
- $elem = $heap->top - zwraca element z góry kopca, nie usuwa tego elementu. Będzie to najmniejszy element z kopca (pod warunkiem, że nie jest używana odwrócona funkcja cmp). Zwraca undef, jeśli kopiec jest pusty.
- $elem = $heap->extract_top - wyciąga i zwraca element z góry kopca, usuwa go z kopca. Zwraca undef, jeśli kopiec jest pusty.
- $heap1->absorb($heap2) - przepisanie wszystkich elementów kopca z $heap2 do $heap1. Powoduje, że $heap2 będzie pusty.
- $heap1->decrease_key($elem) - element zostanie przeniesiony bliżej góry kopca, jeśli jest mniejszy od którychś z jego rodziców (dziadków etc.:). Działanie zależy również od funkcji cmp, jeśli jej działanie jest odwrócone, to element będzie przeniesiony wyżej, gdy będzie większy od którychś z jego rodziców (dziadków etc.:)
- $elem = $heap->delete($elem) - element zostanie usunięty z kopca (bez znaczenia, czy jest on na górze kopca, czu też nie)
Przykłady zastosowań modułu Heap
Ten krótki programik buduje kopiec, następnie wstawia do niego elementy, by na końcu ściągać z niego elementy aż do wyczerpania.
use Heap;
use strict;
my $heap = Heap->new;
my $elem;
use Heap::Elem::Num(NumElem);
foreach $i ( 1..100 ) {
$elem = NumElem( $i );
$heap->add( $elem );
}
while( defined( $elem = $heap->extract_top ) ) {
print "Smallest is ", $elem->val, "\n";
}
Dodatkowe informacje
Jest to moduł przydatny. Pozwala na efektywne przechowywanie danych.
Macierzysta strona dokumentacji do modułu http://search.cpan.org/~jmm/Heap-0.80/lib/Heap.pm
Autor opracowania
Szymon Roziewski
Email: sroziews@manta.univ.gda.pl