java - 寻找更高效的堆排序？

Question

目前我有一个家庭作业问题，内容是:

It is possible to make the heap sort algorithm more efficient by writing a method that will order the entire list at once instead of adding the elements one at a time.

但是我无法弄清楚“而不是一次添加一个元素”到底是什么意思，肯定必须先构建一个堆(这涉及从未排序的列表中逐个添加元素)，然后删除一次从堆中取出最大的一个。

这是我的堆数组:

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

这里是更多HeapSort算法:

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. 我们对输入数组进行 m​​ax-heapify(即，我们重新排列数组中的元素，使其遵循 max-heap 属性。
2. 对于i = n - 1 到 1:
   1. 交换 0 - 数组中带有 i 的第一个元素-第一个元素。
   2. 将堆的大小减少 1(即堆的大小应为 i)。
   3. 执行sift-down对堆进行操作以恢复 max-heap 属性。

请注意，只要 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;
    }
}