heap Class Reference

classe per l'amministrazione dello heap. More...

#include <heap.h>

List of all members.

Public Member Functions
	heap (frequenza **pf, int n)
	il costruttore.
void	down (int i)
	funzione che trascina la testa fino alla posizione giusta.
frequenza *	estrai ()
	funzione per l'estrazione dell'elemento a minore frequenza.
int	lastn ()
	funzione che restituisce l'ultimo indice dell'heap.
void	inserisci (frequenza *f)
	funzione che inserisce un elemento.
void	buildheap ()
	funzione che trasforma un array in un heap
void	up (int i)
	funzione che trascina l'elemento in posizione i nella giusta posizione
Protected Attributes
frequenza **	v
	puntatore all'array che costituisce lo heap.
int	last
	ultimo indice valido dell'array.

---

Detailed Description

classe per l'amministrazione dello heap.

questa classe mi serve per implementare l'algoritmo di huffman, infatti esso necessita di un vero e proprio heap, siccome ho gia disponibile l'array contenente i nodi (con left e right a null) sia nel comrpessore che nel decompressore posso fare un heap di puntatori a nodo ordinati inversamente (il minimo in testa) secondo la frequenza del caratter nel nodo.

See also:

compressore, decompressore, compressore::huffman(), decompressore::huffman()

Definition at line 20 of file heap.h.

---

Constructor & Destructor Documentation

heap::heap (  frequenza **  pf, int  n )

il costruttore. ha come argomento un array di puntatori a frequenza, esso deve già un array a tutti gli effetti quando viene passato al costruttore e questo è vero sia per il compressore, che per il decompressore; non c'è bisogno di distruttore, infatti l'heap viene cancellato direttamente applicando la delete[] sull'argomento attuale di pf, l'array viene trasformato in heap tramite la buildheap(); Complessità: O(n). Parameters: pf  | array di puntatori a frequenza (inizialmente non heap). n  | numero di elementi dell'array. See also: compressore, decompressore, buildheap() Definition at line 12 of file heap.cpp. References buildheap(), last, and v.

---

Member Function Documentation

void heap::buildheap (   )

funzione che trasforma un array in un heap lavora semplicemente invocando la down sui primi n/2 elementi dove n è l'ultimo indice valido (last); Complessità: O(n). See also: heap() Definition at line 68 of file heap.cpp. References down(), and last. Referenced by heap().

void heap::down (  int  i  )

funzione che trascina la testa fino alla posizione giusta. è necessario applicare la down a seguito di una estrazione, infatti nella estrai viene spostato l'ultimo elemento nell'array in testa, e si rendono necessari degli scambi padre figlio per conservare le proprietà dell'heap; Complessità: O(log n). Parameters: i  | elemento su cui fare la down. See also: estrai(), buildheap() Definition at line 19 of file heap.cpp. References last, and v. Referenced by buildheap(), and estrai().

frequenza * heap::estrai (   )

funzione per l'estrazione dell'elemento a minore frequenza. viene semplicemente estratta la testa, dopo di che si riassesta lo heap, viene utilizzata dalle funzioni huffman() presenti in compressore e decompressore per costruire l'albero delle codifiche; Complessità: O(log n). Returns: restituisce il primo elemento dello heap See also: down(), compressore::huffman(), decompressore::huffman() Definition at line 37 of file heap.cpp. References down(), last, and v. Referenced by decompressore::huffman(), and compressore::huffman().

void heap::inserisci (  frequenza *  f  )

funzione che inserisce un elemento. nell'esecuzione della funzione huffman(), bisogna fare molteplici inserimenti e estrazioni, quindi serve la inserisci, essa funziona inserendo dapprima in fondo all'heap l'elemento, poi invocando la up su questo che, tramite scambi padre-figlio, conserva le proprietà dello heap; Complessità: O(log n). Parameters: f  | elemento da inserire. See also: up(), compressore::huffman(), decompressore::huffman() Definition at line 50 of file heap.cpp. References last, up(), and v. Referenced by decompressore::huffman(), and compressore::huffman().

int heap::lastn (   )

funzione che restituisce l'ultimo indice dell'heap. necessaria per conoscere l'ultimo indice dato che l'intero last è privato; Complessità: O(1). Returns: l'ultimo indice valido Definition at line 45 of file heap.cpp. References last. Referenced by compressore::compressore(), and decompressore::decompressore().

void heap::up (  int  i  )

funzione che trascina l'elemento in posizione i nella giusta posizione a partire dall'elemento in posizione i vengono effettuati degli scambi figlio-padre fino a che l'elemento non è in una posizione tale da conservare le proprietà dello heap; Complessità: O(log n). Parameters: i  | indice dell'elemento da sopostare See also: inserisci() Definition at line 56 of file heap.cpp. References v. Referenced by inserisci().

---

Member Data Documentation

frequenza** heap::v [protected]

puntatore all'array che costituisce lo heap. l'array non viene generato dall'heap ma viene passato al costruttore, all'inizio esso non ha una struttura a heap ma basta chiamare la buildheap() e l'array sarà diventato un heap. See also: buildheap() Definition at line 30 of file heap.h. Referenced by compressore::compressore(), decompressore::decompressore(), down(), estrai(), heap(), inserisci(), and up().

---

The documentation for this class was generated from the following files:

• Desktop/Daniele/Program Editing/Progetto di informatica 2/componenti/heap.h
• Desktop/Daniele/Program Editing/Progetto di informatica 2/componenti/heap.cpp

---