Ordinamento di un array utilizzando max-heap in Java

Question

Sto lavorando a un programma che ordina un array dividendolo in max-heap più piccoli ed estraendo il massimo numero intero da ciascuno, quindi eliminandolo dall'heap ed eseguendo di nuovo fino a quando ogni mucchio è vuoto, ma non riesco a capirlo.

Da dove mi trovo il codice sembra buono, ma non ottengo i risultati che sto cercando. Il mio input è creato in modo casuale e crea una matrice di 512 numeri interi. Ecco cosa viene stampato per un'esecuzione di esempio -

Original Array -391 176 -380 -262 -474 327 -496 214 475 -255 50 -351 179 -385 -442 -227 465 127 -293 288 
Sorted Array 475 465 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 
n = 20 k = 2 
The number of comparisons is 243 

Qualcuno può individuare cosa c'è di sbagliato nel mio codice? Sarò davvero felice.

(1) Programma principale

import java.io.File; 
import java.util.*; 
import java.io.FileNotFoundException; 
import java.util.Scanner; 
import java.io.IOException; 

public class Project { 
    static final int n = 20; 
    static final int k = 2; 
    static int counter = 0; 
    private static Scanner scan; 

    public static void main(String[] args) throws IOException { 
     // Optional - reading from a file containing 512 integers. 
     InputCreator.main(); 
     File f = new File("random.txt"); 
     // File f = new File("increase.txt"); 
     // File f = new File("decrease.txt"); 
     try { scan = new Scanner(f); 
     } catch (FileNotFoundException e) { 
      // TODO Auto-generated catch block 
      e.printStackTrace(); } 
     int [] L = new int[n]; 
     System.out.print("Original Array "); 
     for (int i = 0; i < n ; i++) 
      { counter++; L[i] = scan.nextInt(); System.out.print(" " + L[i]); } 
     Projectsort(L); 
    } 

    private static void Projectsort(int [] L) { 
     // int [][] Li = new int [k] [n-(n/k*(k-1))]; // The size of the rest of the integers (n-(n/k*(k-1)) will always be bigger than n/k 
     int [] temp = new int [n/k], extra = new int [n-(n/k)*(k-1)]; 
     int extraIndex = 0, max, maxIndex = 0, r = 0; 
     ProjectMaxHeap [] Li = new ProjectMaxHeap [k]; 
     // The following loop's time effiency is O(k) * O(N/k) = O(N) 
     for (int i=0; i<k-1; i++) { counter++; // copying all the integers from Array L into K-1 smaller arrays 
      for (int j=0; j<n/k ; j++) 
       { counter++; temp [j] = L[i*(n/k)+j]; } 
      Li[i] = new ProjectMaxHeap (temp); } 

     for (int i=(n/k)*(k-1) ; i<n ; ++i) // The rest of the integers on array L 
      { counter++; extra [extraIndex] = L[i]; extraIndex++; } 
     Li[k-1] = new ProjectMaxHeap(extra); 
     System.out.print("\nSorted Array "); 
     for (int i = n ; i > 0 ; i--) { counter++; 
      r = 0; 
      do{max = Li[r].extractMax(); r++; }while(Li[r].isEmpty() && r < k - 1); 
      for (int j = r; j < k; j++) // Time efficiency O(k)*O(N/k) 
      { counter++; 
       if(!Li[j].isEmpty()) { 
       if (Li[j].extractMax() > max) { 
        counter++; 
        max = Li[j].extractMax(); 
        maxIndex = j; } 
      } 
     System.out.print(max + " "); 
     Li[maxIndex].deleteMax(); } } 
     System.out.println("\nn = " + n + " k = " + k +"\nThe number of comparisons is " + counter); 
    } 
} 

(2) Max Mucchio Classe

public class ProjectMaxHeap 
{ 
    private int [] _Heap; 
    private int _size; 

    public ProjectMaxHeap (int [] A){ 
     _size = A.length; 
     _Heap = new int[A.length]; 
     System.arraycopy(A, 0, _Heap, 0, A.length); 
     for (int i = _size/2 ; i >=0 ; i--) { 
      Project.counter++; 
      maxHeapify(i); } 
    } 

    private int parent(int pos) 
    { return pos/2; } 

    private int leftChild(int pos) 
    { return (2 * pos); } 

    private int rightChild(int pos) 
    { return (2 * pos) + 1; } 

    private void swap(int fpos,int spos) { 
     int tmp; 
     tmp = _Heap[fpos]; 
     _Heap[fpos] = _Heap[spos]; 
     _Heap[spos] = tmp; } 

    private void maxHeapify (int i) { 
     int l = leftChild(i), r = rightChild(i), largest; 
     if(l < _size && _Heap[l] > _Heap[i]) { 
      Project.counter+=2; 
      largest = l; } 
      else largest = i; 
     if(r < _size && _Heap[r] > _Heap[largest]) { 
      largest = r; 
      Project.counter+=2; } 
     if (largest != i) { 
      Project.counter++; 
      swap(i, largest); 
      maxHeapify (largest); } 
     } 

    protected boolean isEmpty() { return _size == 0; } 

    protected void deleteMax() { 
     if (_size > 1) { 
      Project.counter++; 
      maxHeapify(0); 
      int max = _Heap[0]; 
      _size--; 
      swap(0, _size); 
      maxHeapify(0); } 
     else _size = 0;  
    } 

    protected int extractMax() { 
     maxHeapify(0); 
     return _Heap[0]; 
    } 
} 

(3) Creatore ingresso

import java.io.BufferedWriter; 
import java.io.File; 
import java.io.FileWriter; 
import java.io.IOException; 
import java.util.*; 
import java.io.FileReader; 
import java.io.BufferedReader; 

public class InputCreator { 
    public static void main() { 
     randomizer(); 
     decrease(); 
     increase(); 
    } 
    private static void randomizer() { 
     // The target file 
     File out = new File("random.txt"); 
     FileWriter fw = null; 
     int n = 0; 
     // Try block: Most stream operations may throw IO exception 
     try { 
      // Create file writer object 
      fw = new FileWriter(out); 
      // Wrap thק writer with buffered streams 
      BufferedWriter writer = new BufferedWriter(fw); 
      int line; 
      Random random = new Random(); 
      while (n < Project.n) { 
       // Randomize an integer and write it to the output file 
       line = random.nextInt(1000)-500; 
       writer.write(line + "\r\n"); 
       n++; 
      } 
      // Close the stream 
      writer.close(); 
     } catch (IOException e) { 
      e.printStackTrace(); 
      System.exit(0); 
     } 
    } 
    private static void increase() { 
     // The target file 
     File out = new File("increase.txt"); 
     FileWriter fw = null; 
     int n = 0; 
     int temp = 0; 
     // Try block: Most stream operations may throw IO exception 
     try { 
      // Create file writer object 
      fw = new FileWriter(out); 
      // Wrap thק writer with buffered streams 
      BufferedWriter writer = new BufferedWriter(fw); 
      int line; 
      Random random = new Random(); 
      while (n < Project.n) { 
       // Randomize an integer and write it to the output file 
       line = random.nextInt((n+1)*10); 
       if(line > temp) { 
       writer.write(line + "\r\n"); 
       n++; 
       temp = line; } 
      } 
      // Close the stream 
      writer.close(); 
     } catch (IOException e) { 
      e.printStackTrace(); 
      System.exit(0); 
     } 
    } 
     private static void decrease() { 
     // The target file 
     File out = new File("decrease.txt"); 
     FileWriter fw = null; 
     int n = 0; 
     int temp = 10000; 
     // Try block: Most stream operations may throw IO exception 
     try { 
      // Create file writer object 
      fw = new FileWriter(out); 
      // Wrap thק writer with buffered streams 
      BufferedWriter writer = new BufferedWriter(fw); 
      int line; 
      Random random = new Random(); 
      while (n < Project.n) { 
       // Randomize an integer and write it to the output file 
       line = 10000 - random.nextInt((n+1)*20); 
       if(line < temp) { 
       writer.write(line + "\r\n"); 
       n++; 
       temp = line; } 
      } 
      // Close the stream 
      writer.close(); 
     } catch (IOException e) { 
      e.printStackTrace(); 
      System.exit(0); 
     } 
    } 
} 

Answer 1

Il problema è con max = Li[0].extractMax(); Non stai verificando se Li[0] potrebbe essere vuoto.

Controllare sempre i prerequisiti e fail fast. Il problema sarebbe diventato immediatamente evidente aveva iniziato si extractMax e deleteMax con

if (_size == 0) { 
    throw new IllegalStateException("empty heap"); 
} 

Ecco il ciclo finale fisso:

for (int i = 0; i < n; i++) { 
    int maxIndex = -1;   // remove these variable declarations from top of method 
    int max = Integer.MIN_VALUE; // it's best to confine variables to narrow scope 
    for (int j = 0; j < k; j++) { 
     if (!Li[j].isEmpty()) { 
      int current = Li[j].extractMax(); 
      if (maxIndex == -1 || current > max) { 
       maxIndex = j; 
       max = current; 
      } 
     } 
    } 
    assert maxIndex != -1; 
    Li[maxIndex].deleteMax(); 
    System.out.print(max + " "); 
}