编辑代码

import java.util.ArrayList;
import java.util.List;

class Heap{
    private int size;
    private List<Integer> heap;
    private List<Integer> sorted;

    public Heap(int[] nums) {
        this.size = nums.length;
        int[] newNums = new int[nums.length + 1];
        for (int i = 1; i < newNums.length; i++){
            newNums[i] = nums[i - 1];
        }
        for (int i = 1; i < newNums.length / 2 + 1; i++){
            int nowIndex = i;
            while (nowIndex >= 1){
                if (newNums[nowIndex] < newNums[nowIndex * 2] ||
                        newNums[nowIndex] < newNums[nowIndex * 2 + 1]){
                    int largeIndex = nowIndex * 2 + 1 >= newNums.length ||
                            newNums[nowIndex * 2] > newNums[nowIndex * 2 + 1]?
                            nowIndex * 2:nowIndex * 2 + 1;
                    int t = newNums[largeIndex];
                    newNums[largeIndex] = newNums[largeIndex / 2];
                    newNums[largeIndex / 2] = t;
                    nowIndex = nowIndex / 2;
                }else {
                    break;
                }
            }
        }
        this.heap = new ArrayList<>();
        for (int i = 1; i < newNums.length; i++){
            this.heap.add(newNums[i]);
        }
    }

    public List<Integer> getHeap() {
        return heap;
    }

    public void heapSort(){
        this.sorted = new ArrayList<>();
        int sortSize = size + 1;
        List<Integer> sortHeap = new ArrayList<>();
        sortHeap = getNewList(this.heap, sortHeap);

        while (sortHeap.size() >= 2){
            int index = 1;
            Integer root = sortHeap.get(index);
            int last = sortHeap.remove(sortHeap.size() - 1);
            this.sorted.add(root);

            while (index * 2 < sortHeap.size()){
                index = index * 2 + 1 >= sortHeap.size() ||
                        sortHeap.get(index * 2) > sortHeap.get(index * 2 + 1)?
                        index * 2:index * 2 + 1;
                sortHeap.set(index / 2, sortHeap.get(index));
            }
            if (sortHeap.size() >= 2) {
                sortHeap.set(index, last);
            }
        }
    }

    public List<Integer> getSorted() {
        heapSort();
        return sorted;
    }

    public List<Integer> getNewList(List<Integer> list1, List<Integer> list2){
        list2.add(0);
        list2.addAll(list1);
        return list2;
    }
}