Sắp xếp một mảng bằng cách sử dụng tối đa heap trong Java

Question

Tôi đang làm việc trên một chương trình sắp xếp mảng bằng cách chia mảng thành các phần tối đa nhỏ hơn và giải nén số nguyên tối đa ra khỏi mỗi mảng, sau đó xóa nó khỏi heap và đang chạy một lần nữa cho đến khi mọi đống trống rỗng, nhưng tôi không thể hình dung ra được.

Từ đó tôi đứng mã có vẻ tốt, nhưng tôi không nhận được kết quả mà tôi đang tìm kiếm. Đầu vào của tôi được tạo ngẫu nhiên và tạo một mảng gồm 512 số nguyên. Dưới đây là những gì nó in cho một ví dụ chạy -

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 

Có ai phát hiện thấy mã của tôi có vấn đề gì không? Tôi sẽ rất vui.

(1) Chương trình chính

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 Heap Lớp

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) Đầu vào Đấng Tạo Hóa

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

Vấn đề là với max = Li[0].extractMax(); Bạn không kiểm tra xem Li[0] có thể để trống không.

Luôn kiểm tra các điều kiện tiên quyết và fail fast. Vấn đề sẽ trở nên rõ ràng ngay lập tức bạn đã bắt đầu extractMax và deleteMax với

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

Đây là vòng chung kết cố định:

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 + " "); 
}