[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) ? :mbe:

[71104]

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

[EnricoilP]

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]

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

Sì, è 2*i + 1

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

Ed è una cosa scabrosa?:eek:

[banryu79]

Ed è una cosa scabrosa?:eek:


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

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



* modo di dire tibetano

[khelidan1980]

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

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]

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

Ah.

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]

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]

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.