在Java中使用max-heap对数组进行排序

Question

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

从我的立场来看，代码看起来不错，但我没有得到我想要的结果。我的输入是随机创建的，并生成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);
        }
    }
}

Answer 1

问题出在max=Li[0]. extetMax（）；您没有检查Li[0]是否为空。

始终检查前提条件并快速失败。如果您开始使用

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