Massive Algorithms: Implementing Heapsort in Java and C

Implementing Heapsort in Java and C · Edd Mann
the first step is to create a heap structure from the input. Calling the ‘heapify’ method on the first half of the input array guarantees (by recursion) to build up the heap data structure and fulfill the heap property. Once this step has completed we loop through each item in the heap, swapping the first and last heap elements, reducing and reconstructing the structure after each iteration.

public class Heap {

    private static int total;

    private static void swap(Comparable[] arr, int a, int b)
    {
        Comparable tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    private static void heapify(Comparable[] arr, int i)
    {
        int lft = i * 2;
        int rgt = lft + 1;
        int grt = i;

        if (lft <= total && arr[lft].compareTo(arr[grt]) > 0) grt = lft;
        if (rgt <= total && arr[rgt].compareTo(arr[grt]) > 0) grt = rgt;
        if (grt != i) {
            swap(arr, i, grt);
            heapify(arr, grt);
        }
    }

    public static void sort(Comparable[] arr)
    {
        total = arr.length - 1;

        for (int i = total / 2; i >= 0; i--)
            heapify(arr, i);

        for (int i = total; i > 0; i--) {
            swap(arr, 0, i);
            total--;
            heapify(arr, 0);
        }
    }
}

http://www.sanfoundry.com/java-program-implement-heap-sort/

```
public class HeapSort 
```
```
{    
```
```
    private static int N;
```
```
    /* Sort Function */
```
```
    public static void sort(int arr[])
```
```
    {       
```
```
        heapify(arr);        
```
```
        for (int i = N; i > 0; i--)
```
```
        {
```
```
            swap(arr,0, i);
```
```
            N = N-1;
```
```
            maxheap(arr, 0);
```
```
        }
```
```
    }     
```
```
    /* Function to build a heap */   
```

    public static void heapify(int arr[])

```
    {
```
```
        N = arr.length-1;
```
```
        for (int i = N/2; i >= 0; i--)
```
```
            maxheap(arr, i);        
```
```
    }
```

    /* Function to swap largest element in heap */

    public static void maxheap(int arr[], int i)

```
    { 
```
```
        int left = 2*i ;
```
```
        int right = 2*i + 1;
```
```
        int max = i;
```

        if (left <= N && arr[left] > arr[i])

```
            max = left;
```

        if (right <= N && arr[right] > arr[max])

```
            max = right;
```
```
 
```
```
        if (max != i)
```
```
        {
```
```
            swap(arr, i, max);
```
```
            maxheap(arr, max);
```
```
        }
```
```
    }    
```

    /* Function to swap two numbers in an array */

    public static void swap(int arr[], int i, int j)

```
    {
```
```
        int tmp = arr[i];
```
```
        arr[i] = arr[j];
```
```
        arr[j] = tmp; 
```
```
    }      
```
```
}
```

http://www.code2learn.com/2011/09/heapsort-array-based-implementation-in.html

http://massivealgorithms.blogspot.com/2015/08/heapsort-vs-quicksort.html
3.1 为什么堆排比快排慢

回顾一下堆排的过程：

1. 建立最大堆（堆顶的元素大于其两个儿子，两个儿子又分别大于它们各自下属的两个儿子… 以此类推）

2. 将堆顶的元素和最后一个元素对调（相当于将堆顶元素（最大值）拿走，然后将堆底的那个元素补上它的空缺），然后让那最后一个元素从顶上往下滑到恰当的位置（重新使堆最大化）。

3. 重复第2步。

这里的关键问题就在于第2步，堆底的元素肯定很小，将它拿到堆顶和原本属于最大元素的两个子节点比较，它比它们大的可能性是微乎其微的。实际上它肯定小于其中的一个儿子。而大于另一个儿子的可能性非常小。于是，这一次比较的结果就是概率不均等的，根据前面的分析，概率不均等的比较是不明智的，因为它并不能保证在糟糕情况下也能将问题的可能性削减到原本的1/2。可以想像一种极端情况，如果a肯定小于b，那么比较a和b就会什么信息也得不到——原本剩下多少可能性还是剩下多少可能性。

在堆排里面有大量这种近乎无效的比较，因为被拿到堆顶的那个元素几乎肯定是很小的，而靠近堆顶的元素又几乎肯定是很大的，将一个很小的数和一个很大的数比较，结果几乎肯定是“小于”的，这就意味着问题的可能性只被排除掉了很小一部分。

这就是为什么堆排比较慢（堆排虽然和快排一样复杂度都是O(NlogN)但堆排复杂度的常系数更大）。

MacKay也提供了一个修改版的堆排：每次不是将堆底的元素拿到上面去，而是直接比较堆顶（最大）元素的两个儿子，即选出次大的元素。由于这两个儿子之间的大小关系是很不确定的，两者都很大，说不好哪个更大哪个更小，所以这次比较的两个结果就是概率均等的了。具体参考这里。

http://users.aims.ac.za/~mackay/sorting/sorting.html

Read full article from Implementing Heapsort in Java and C · Edd Mann

Implementing Heapsort in Java and C · Edd Mann

Labels

Popular Posts