寻找更有效的堆排序？

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-heapify输入数组（即我们重新安排数组中的元素，使其如下最大堆性能
2. 对于i = N - 1至1：
   1. 交换与i个元件的阵列中的第0元件
   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; 
    } 
}