我正在开发一个程序，该程序通过将数组分成较小的最大堆并从每个堆中提取最大整数，然后将其从堆中删除并再次运行直到每个堆都为空来对数组进行排序，但是我似乎无法弄清楚。

从我的角度来看，代码看起来不错，但我没有得到我正在寻找的结果。我的输入是随机创建的，并构成一个包含 512 个整数的数组。这是它为一个示例运行打印的内容 -

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

谁能发现我的代码有什么问题？我会很高兴。

(1) 主程序

 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) 最大堆类

    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) 输入创建器

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

最佳答案

问题在于 max = Li[0].extractMax(); 您没有检查 Li[0] 是否为空。

始终检查先决条件和 fail fast .如果您使用 extractMax 和 deleteMax 启动

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

这是固定的最终循环:

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

关于java - 在 Java 中使用最大堆对数组进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30361151/