查找更有效的堆排序

Question

当前 我有一个家庭作业问题，上面写着：

可以通过以下方法使堆排序算法更有效 编写一个将一次对整个列表进行排序的方法，而不是 一次添加一个元素。

但是，我无法弄清楚"而不是一次添加一个元素"的确切含义，当然必须首先构建一个堆（这涉及从未排序的列表中逐个添加元素），然后一次从堆中删除最大的元素一个。

这是我的堆数组：

import exceptions.exceptions.*;
public class ArrayHeap<T> extends ArrayBinaryTree<T> implements HeapADT<T> {
    public ArrayHeap(){
        super();
    }
    public void addElement (T element){
        if (count==size())
            expandCapacity();
        tree[count] = element;
        count++;
        if (count > 1)
            heapifyAdd();
    }
    private void heapifyAdd(){
        int index = count - 1;
        while ((index != 0) && (((Comparable)tree[index]).compareTo(tree[(index-1)/2]) < 0))
        {
            T temp = tree[index];
            tree[index] = tree[(index-1)/2];
            tree[(index-1)/2] = temp;
            index = (index-1)/2;
        }
    }
    public T removeMin(){
        if (isEmpty())
            throw new EmptyCollectionException ("Empty Heap");
        T minElement = findMin();
        tree[0] = tree[count-1];
        heapifyRemove();
        count--;
        return minElement;
    }
    private void heapifyRemove()
    {
        T temp;
        int node = 0;
        int left = 1;
        int right = 2;
        int next;
        if ((tree[left] == null) && (tree[right] == null))
           next = count;
        else if (tree[left] == null)
           next = right;
        else if (tree[right] == null)
           next = left;
        else if (((Comparable)tree[left]).compareTo(tree[right]) < 0)
           next = left;
        else
           next = right;
        while ((next < count) && (((Comparable)tree[next]).compareTo(tree[node]) < 0)){
                temp = tree[node];
                tree[node] = tree[next];
                tree[next] = temp;
                node = next;
                left = 2*node + 1;
                right = 2*(node+1);
                if ((tree[left] == null) && (tree[right] == null))
                   next = count;
                else if (tree[left] == null)
                   next = right;
                else if (tree[right] == null)
                   next = left;
                else if (((Comparable)tree[left]).compareTo(tree[right]) < 0)
                   next = left;
                else
                   next = right;
            }
    }
    public T findMin() {
        if (isEmpty())
           throw new EmptyCollectionException ("Empty Heap");
        return tree[0];
    }
}

以下是更多堆排序算法：

import ArrayHeap;
public class HeapSort<T>{
    public T[] heapsort(T[] data, int min, int max){
        ArrayHeap<T> temp = new ArrayHeap<T>();
        for (int c = min; c <= max; c++){
            temp.addElement(data[c]);
        }
        int count = min;
        while(!(temp.isEmpty())){
            T jj = temp.removeMin();
            data[count] = jj;
            count ++;
        }
        return data;
    }

Answer 1

执行堆排序最直接的方法是使用单独的堆并将所有元素添加到其中，然后当我们逐个弹出元素时，这些元素将按顺序排列。这就是语句中"一次添加一个元素"所指的，这就是您的实现正在做的事情：创建一个 ArrayHeap 类型的堆并将data元素插入其中，最后将元素弹出回data。

一种更有效的方法（就空间和时间而言）是执行就地排序，我们使用要排序的数组作为堆，而不是为堆使用额外的内存，这就是"一次对整个列表进行排序"所指的。此实现的步骤如下，我们将按非递减顺序对元素进行排序：

1. 我们对输入数组进行最大堆积（即我们重新排列数组中的元素，使其遵循 max-heap 属性。
2. 对于 i = n - 1 到 1：
   将
   1. 数组中的第 0 个元素与第 i 个元素交换。
   2. 将堆的大小减小 1（即堆的大小应为 i ）。
   3. 对堆执行sift-down操作以还原最大堆属性。

请注意，每当 max-heap 属性成立时，堆中最顶层的元素就是最大的元素，因此在第 k 次迭代开始时（此处k = n - i），第 0 个元素是 k -最大的元素，我们通过交换将元素放置在数组中的正确位置。

注意步骤1可以在O(n)中完成，在步骤2中有O(n)次迭代，每个sift-down操作都需要时间O(log(n))，所以整体时间复杂度是O(n log(n))。

下面是一个 Java 中的实现，供您参考：

import java.util.Random;
public class HeapSort {
    public static void main(String[] args) {
        for (int i = 1; i <= 10; i++) {
            System.out.println(String.format("Iteration number %d%n", i));
            Integer[] array = randomIntArray(10, 0, 100);
            System.out.println(String.format("Array before sorting: [%s]", toStr(array)));
            heapSort(array);
            System.out.println(String.format("Array after sorting: [%s]", toStr(array)));
            System.out.println("================================================================");
        }
    }
    private static <T extends Comparable<T>> T[] heapSort(T[] array) {
        maxHeapify(array, array.length);
        for (int i = array.length - 1; i > 0; i--) {
            swap(array, 0, i);
            siftDown(array, i, 0);
        }
        return array;
    }
    private static <T extends Comparable<T>> void maxHeapify(T[] array, int heapSize) {
        for (int i = getParentIdx(heapSize - 1); i >= 0; i--) {
            siftDown(array, heapSize, i);
        }
    }
    private static <T extends Comparable<T>> void siftDown(T[] array, int heapSize, int idx) {
        final int length = Math.min(array.length, heapSize) - 1;
        if (idx > length || idx < 0) throw new IllegalArgumentException("Index out of range");
        while (true) {
            int maxIdx = idx;
            int leftChildIdx = getLeftChildIdx(idx);
            int rightChildIdx = getRightChildIdx(idx);
            if (leftChildIdx <= length && array[maxIdx].compareTo(array[leftChildIdx]) < 0) maxIdx = leftChildIdx;
            if (rightChildIdx <= length && array[maxIdx].compareTo(array[rightChildIdx]) < 0) maxIdx = rightChildIdx;
            if (idx != maxIdx) {
                swap(array, idx, maxIdx);
                idx = maxIdx;
            } else {
                return;
            }
        }
    }
    private static int getParentIdx(int idx) {
        return (idx - 1) / 2;
    }
    private static int getLeftChildIdx(int idx) {
        return idx * 2 + 1;
    }
    private static int getRightChildIdx(int idx) {
        return idx * 2 + 2;
    }
    private static <T> void swap(T[] array, int i, int j) {
        T tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    private static <T> String toStr(T[] array) {
        StringBuilder sb = new StringBuilder();
        for (T element : array) {
            sb.append(element + ", ");
        }
        return sb.substring(0, sb.length() - 2);
    }
    private static Integer[] randomIntArray(int size, int lowerBound, int upperBound) {
        Integer[] result = new Integer[size];
        Random random = new Random();
        int diff = upperBound - lowerBound + 1;
        for (int i = 0; i < size; i++) result[i] = lowerBound + random.nextInt(diff);
        return result;
    }
}