Ciao,
allora oggi ho scritto una classe che gestisce un HEAP che poi mi servirà per implementare l'algoritmo di ordinamento heapsort.
Escludendo tutti i dettagli algoritmici (che sono giusti e che ho studiato al corso di algoritmi e sono anche un po' complessi) tale classe funziona circa così così:
La struttura dati HEAP viene implementata per mezzo di un normalissimo array chiamato appunto heap.
Il costruttore riceve un generico array arr come parametro ed inizialmente lo copia dentro all'array heap (facendo però partire gli elementi dalla posizione 1 e non dalla posizione 0).
Poi grazie al metodo ricorsivo heapify() il contenuto di heap viene rimaneggiato e trasformato in un vero e proprio HEAP (che è un array che rispetta determinate condizioni matematiche). La procedura heapify() a sua volta fà uso di un altro metodo ricorsivo chiamata fixheap().
Poi c'è un metodo stampa() che dovrebbe stampare il contenuto dell'array heap()
Il problema è che non stampa nulla...ho come l'impressione che per qualche errore non mi popoli l'array heap.
Il codice della classe è il seguente:
Se il problema fosse come ho ipotizzato che non popola l'array heap...l'errore potrebbe stare:codice:<?php /* Classe che implementa la struttura dati HEAP e la sua funzionalità per l'ordinamento di una collezione mediante l'algoritmo di ordinamento Heap Sort */ class Heap{ /* Variabile di istanza che implementa la struttura dati ad albero dell'heap per mezzo di un array */ private $heap = array(); private $heapSize = 0; // Numero di elementi correntemente dentro l'HEAP /* Costruttore: Crea un nuovo oggetto istanza di Heap. Riceve un qualunque array come parametro di input, lo copia dentro alla variabile di istanza heap[] (mettendoli dentro l'array Heap a partire dalla posizione 1) e su di esso richiama ilmetodo di classe heapify per trasformarlo in loco in un heap */ public function __construct($arr){ /* Scorre l'array ricevuto come parametro e lo copia nel'array heap traslando gli elementi una posizione in avanti (per farli partire dalla posizione 1 e non 0) */ foreach($arr as $chiave => $valore){ $heap[$chiave+1] = $arr[chiave]; // Copia gli elementi traslandoli $heapSize ++; //Incrementa di 1 il numero elementi inseriti nell'heap } /* Invoca il metodo heapify sull'array partendo dalla prima posizione che sarà trasformato in un HEAP */ $this->heap = $this->heapify($heap, 1); echo $heap[1]; } /* Metodo che dato un qualsiasi array lo riarrangia trasformandolo in una struttura dati HEAP memorizzata sempre nello stesso array di partenza */ private function heapify($heap, $nodo_i){ echo "heapify è stata chiamata "; /* CASO BASE: Se heap è vuoto ritorna al chiamante */ if($this->sinistro($nodo_i) > $this->heapSize) return; /* Altrimenti procedi ricorsivamente nel seguente modo */ else{ $sin = sinistro($nodo_i); // Posizione della radice del sottoalbero sinistro $des = destro($nodo_i); // Posizione della radice del sottoalbero destro $nodoCorrente = $sin; heapify($heap, $nodoCorrente); // Chiama ricorsivamente sul sottoalbero sinistro $nodoCorrente = $des; heapify($heap, $nodoCorrente); // Chiama ricorsivamente sul sottoalbero destro fixHeap($nodoCorrente, $heap); } } /* Metodo che prende in input un quasi heap (cioè un heap con al più un'anomalia) ed un indice nodo_i e restituisce un heap corretto */ private function fixHeap($nodo_i, $quasiHeap){ $sin; // Conterrà l'indice del figlio sinistro $des; // Conterrà l'indice del figlio destro $max; // Conterrà l'indice del figlio avente valore massimo /* Se nodo_i è una foglia allora ritorna al chiamante (caso base)*/ if(sinistro($nodo_i) > $this->$heapSize) return; /* Se nodo_i non è una foglia */ else{ $sin = sinistro($nodo_i); // Posizione del figlio sinistro $des = destro($nodo_i); // Posizione del figli destro /* Trova il massimo tra il figlio sinistro e destro di nodo_i */ if($quasiHeap[sin] >= $quasiHeap[$des]) $max = $sin; else $max = $des; /* Se il valore in posizione nodo_i è MINORE del valore del figlio massimo */ if($quasiHeap[$nodo_i] < $quasiHeap[$max]){ $tmp = $quasiHeap[$nodo_i]; // Salva il valore in posizione i /* Scambia il valore in posizione nodo_i con il valore in posizione max */ $quasiHeap[$nodo_i] = $quasiHeap[max]; $quasiHeap[$max] = $tmp; /* Invoca ricorsivamente il metodo fixHeap() passandogli come parametro lo stesso array e la posizione max */ fixHeap($max, $quasiHeap); } } } /* Metodo che dato l'indice di un elemento dell'heap calcola l'indice del suo figlio sinistro nell'heap */ private function sinistro($indicePadre){ $sin = $indicePadre*2; // Calcola l'indice del figlio sinistro return $sin; // Ritorna il valore di sin al chiamante } /* Metodo che dato l'indice di un elemento dell'heap calcola l'indice del suo figlio destro nell'heap */ private function destro($indicePadre){ $des = $indicePadre*2 + 1; // Calcola l'indice del figlio destro return $padre; // Ritorna il valore di des al chiamante } /* Metodo che dato un elemento dell'heap calcolal'indice del padre */ private function padre($indiceNodo){ $padre = floor(i/2); // Calcola la parte intera return $padre; // Ritorna al chiamante la posizione del padre } /* Metodo per stampare l'heap */ public function stampaHeap(){ echo $heap[1]; } } $arr = array(70,10, 14, 18, 11, 27); echo "Array originale <br \>\n"; foreach($arr as $chiave => $valore){ echo $valore." "; } $myHeap = new Heap($arr); $myHeap->stampaHeap(); ?>
1) Nel ciclo foreach che copia gli elementi di $arr dentro $heap traslandoli di una posizione.
2) Oppure in qualcosa che riguarda le procedure ricorsive...e allora là credo sia da spararsi risolvere...
Qualche anima pia mi sà dare una mano?
Sapere inoltre se esiste un valido (e possiblmente non troppo complicato) debbugger per il codice PHP?
Grazie
Andrea
Rispondi quotando
