설명#

The heap sort is the slowest of the O(n log n) sorting algorithms, but unlike the merge and quick sorts it doesn't require massive recursion or multiple arrays to work. This makes it the most attractive option for very large data sets of millions of items.

The heap sort works as it name suggests - it begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap and removes the largest remaining item and places it in the next open position from the end of the sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.

To do an in-place sort and save the space the second array would require, the algorithm below "cheats" by using the same array to store both the heap and the sorted array. Whenever an item is removed from the heap, it frees up a space at the end of the array that the removed item can be placed in.

As mentioned above, the heap sort is slower than the merge and quick sorts but doesn't use multiple arrays or massive recursion like they do. This makes it a good choice for really large sets, but most modern computers have enough memory and processing power to handle the faster sorts unless over a million items are being sorted.

The "million item rule" is just a rule of thumb for common applications - high-end servers and workstations can probably safely handle sorting tens of millions of items with the quick or merge sorts. But if you're working on a common user-level application, there's always going to be some yahoo who tries to run it on junk machine older than the programmer who wrote it, so better safe than sorry.

  • 장점: In-place and non-recursive, making it a good choice for extremely large data sets.
  • 단점: Slower than the merge and quick sorts.

실행횟수

O(n log n)

자바 소스#

public class HeapSort {

  public static void sort(int numbers[]) {
    int i, temp;
    int array_size = numbers.length;

    for (i = (array_size / 21; i >= 0; i--)
      siftDown(numbers, i, array_size);

    for (i = array_size - 1; i >= 1; i--) {
      temp = numbers[0];
      numbers[0= numbers[i];
      numbers[i= temp;
      siftDown(numbers, 0, i - 1);
    }
  }

  public static void siftDown(int numbers[]int root, int bottom) {
    int done, maxChild, temp;

    done = 0;
    while ((root * <= bottom&& (!= done)) {
      if (root * == bottom)
        maxChild = root * 2;
      else if (numbers[root * 2> numbers[root * 1])
        maxChild = root * 2;
      else
        maxChild = root * 1;

      if (numbers[root< numbers[maxChild]) {
        temp = numbers[root];
        numbers[root= numbers[maxChild];
        numbers[maxChild= temp;
        root = maxChild;
      else
        done = 1;
    }
  }

  public static void main(String[] args) {
    int[] a = 4731582};
    sort(a);
    for (int i = 0; i < a.length; i++)
      System.out.print(a[i"  ");
  }
}

효율성#

heap.jpg

Add new attachment

Only authorized users are allowed to upload new attachments.

List of attachments

Kind Attachment Name Size Version Date Modified Author Change note
jpg
heap.jpg 29.4 kB 1 14-Jul-2007 22:16 DongGukLee
« This page (revision-1) was last changed on 14-Jul-2007 22:16 by DongGukLee