[java] max-heap

[EnricoilP]

Ciao a tutti,

Sono due ore che sbatto la testa contro questo pezzo di codice. Data una lista di interi, devo restituire una max-heap.

import java.util.Arrays;

public class MaxHeap {

	private int[] m_Heap;
	private int m_Size;

	// costruttori
	public MaxHeap(int[] in) 
	{
		m_Size = in.length;
		m_Heap = in;
		buildHeap();
	}

	public void buildHeap() {
		for (int i = (int) ((m_Heap.length / 2) ); i >= 0; i--) {
			heapify(i);
		}
	}

	private void heapify(int i) {
		int l = left(i);
		int r = right(i);
		int largest = 0;
		if ((l < m_Size)&& (m_Heap[l] > m_Heap[i])){
			largest = l;
		} 
		else {
			largest = i;
		}
		if ((r < m_Size) && (m_Heap[r] > m_Heap[largest])){
			largest = r;
		}
		if (largest != i){
			int swap = m_Heap[i];
			m_Heap[i] = m_Heap[largest];
			m_Heap[largest] = swap;
			heapify(largest);
		}
	}

	private int left(int i) {
		return 2 * i;
	}

	private int right(int i) {
		return 2 * i + 1;
	}

	public String toString() {
		return Arrays.toString(m_Heap);
	}


	public static void main(String[] args) {
		MaxHeap myHeap = new MaxHeap(myArray);
		System.out.println(myHeap.toString());
	}

	static int[] myArray = {43,9,68,50,57,51,36,27,89,73,87,57,15,18,55};

Mi restituisce: [89, 87, 73, 55, 68, 57, 36, 50, 57, 43, 51, 9, 15, 18, 27]
... dove 55 ha come figli 50 e 57.

Non riesco proprio a vedere l'errore...

Vi ringrazio!

[wizard_at]

mi scusa per la mia niubba niubbaggine...cosa e'un "max-heap"??

[71104]

sicuro che per ottenere l'altro figlio fosse 2 * i + 1 e non 2 * (i + 1) ?

[71104]

oggesù, ora che ci faccio caso... hai usato la notazione ungherese in Java...

[EnricoilP]

Originariamente inviato da wizard_at

mi scusa per la mia niubba niubbaggine...cosa e'un "max-heap"??

In parole povere è una struttura dati astratta rappresentata da un array (che puo' essere visto come un albero binario) in cui ogni elemento i è maggiore o uguale dell'elemento i*2 e dell'elemento i*2 + 1. "i" è il padre, "i*2" e "i*2 + 1" sono i due figli.

[EnricoilP]

Originariamente inviato da 71104

sicuro che per ottenere l'altro figlio fosse 2 * i + 1 e non 2 * (i + 1) ?

Sì, è 2*i + 1

Originariamente inviato da 71104

oggesù, ora che ci faccio caso... hai usato la notazione ungherese in Java...

Ed è una cosa scabrosa?

[banryu79]

Originariamente inviato da EnricoilP

Ed è una cosa scabrosa?

Diciamo che è come mettere la testa di uno yak sul corpo di una pecora*...

Sarebbe meglio usare lo stile camelCase e le naming convention tipiche di Java



* modo di dire tibetano

[khelidan1980]

Originariamente inviato da banryu79

Diciamo che è come mettere la testa di uno yak sul corpo di una pecora*...

Sarebbe meglio usare lo stile camelCase e le naming convention tipiche di Java



* modo di dire tibetano

mi son sempre chiesto perchè camelCase....la gobba del cammello lol....

inoltre credo la notazione unghererese si allontani anche dal paradigma oo,cosa starebbe a rappresentare un oggetto di nome "myArray" ad esempio?

[EnricoilP]

Originariamente inviato da banryu79

Sarebbe meglio usare lo stile camelCase e le naming convention tipiche di Java

Ah.

Originariamente inviato da khelidan1980

inoltre credo la notazione unghererese si allontani anche dal paradigma oo,cosa starebbe a rappresentare un oggetto di nome "myArray" ad esempio?

myArray non è camel case? Comunque mi pare chiaro che rappresenti un array di esempio su cui testare la classe...da qui "myArray". Cosa avrei dovuto scriverci?
Comunque, non sarà di certo quello ad aver indispettito il compilatore.

[khelidan1980]

Originariamente inviato da EnricoilP

Ah.



myArray non è camel case? Comunque mi pare chiaro che rappresenti un array di esempio su cui testare la classe...da qui "myArray". Cosa avrei dovuto scriverci?
Comunque, non sarà di certo quello ad aver indispettito il compilatore.

no forse mi son spiegato male,e si camelCase ma intendevo che non è molto OO,quell'oggetto cosa rappresenta del mondo reale?
Poi è più un discorso generale non focalizzato sue queste poche righe di esempio,dicevo che la notazione ungherese poco ci azzecca con il paradigma OO

[EnricoilP]

Originariamente inviato da khelidan1980

no forse mi son spiegato male,e si camelCase ma intendevo che non è molto OO,quell'oggetto cosa rappresenta del mondo reale?

Rappresenta la configurazione di non so quanti flip-flop, se è nella memoria centrale, ma non vedo cosa c'entri. Puoi essere un po' più chiaro? Grazie.

[banryu79]

Forse khelidan1980 voleva semplicemente dire che nominare un array di interi col nome "myArray" non dice molto al lettore del codice, dato che lo vede da se che è un array di interi e forse si poteva trovargli un nome più significativo.

Comunque credo anche parlasse in senso più generale, va da se che nel caso uno scriva una piccola porzione di codice per delle prove e uso personale non è necessario che si soffermi ogni volta a spendere 5 min per trovare il nome più sgnificativo possibile per ogni cosa.