排序算法之堆排序！

堆是一种特殊的树，只要满足这两点，它就是一个堆。

  • 堆是一个完全二叉树。
  • 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

对于每个节点的值都大于等于子树中每个节点值的堆，叫做大顶堆。

对于每个节点的值都小于等于子树中每个节点值的堆，叫做小顶堆。

一般升序用大根堆，降序就用小根堆。

如何实现一个堆

完全二叉树比较适合用数组来存储。

用数组来存储完全二叉树是非常节省存储空间的。

因为不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

比如查找数组arr中某个数的父结点和左右孩子结点，比如已知索引为i的数，那么：

  • 父结点索引：(i-1)/2

  • 左孩子索引：2*i+1

  • 右孩子索引：2*i+2

所以堆的定义性质：

  • 大根堆：arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)

  • 小根堆：arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)

堆排序基本步骤

首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端。

将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1。

将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组。

以下将针对数组arr[1,2,5,4,3,7]进行大顶堆的数据结构转换。

从最后一个非叶子结点开始（第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是索引为2的结点）。

  • 从右至左，从下至上进行调整。

由于[5,7]中7元素最大，5和7交换。

最后一个非叶子结点索引减1，找到第二个非叶结点(索引1)，由于[4,3,2]中4元素最大，2和4交换。

非叶子结点索引减1，找到第三个非叶结点(索引0)，由于[4,1,7]中7元素最大，1和7交换。

这时，交换导致了子根[1,5]结构混乱，继续调整，[1,5]中5最大，交换1和5。

此时，我们就将一个无序序列构造成了一个大顶堆。

将堆顶元素与末尾元素进行交换，使末尾元素最大。

然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

最后，就实现了堆排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.Arrays;
 
public class HeapSort {
  public static void main(String[] args) {
    int data[] = { 8, 4, 20, 7, 3, 1, 25, 14, 17 };
    heapSort(data);
    System.out.println(Arrays.toString(data));
  }
 
  public static void maxHeap(int data[], int start, int end) { 
 
    int parent = start;
    int son = parent * 2 + 1; // 下标是从0开始的就要加1，从1就不用
    while (son < end) {
      int temp = son;
      // 比较左右节点和父节点的大小
      if (son + 1 < end && data[son] < data[son + 1]) { // 表示右节点比左节点大
        temp = son + 1; // 就要换右节点跟父节点
      }
      // temp表示的是 我们左右节点大的那一个
      if (data[parent] > data[temp])
        return; // 不用交换
      else { // 交换
        int t = data[parent];
        data[parent] = data[temp];
        data[temp] = t;
        parent = temp; // 继续堆化
        son = parent * 2 + 1;
      }
    }
    return;
 
  }
 
  public static void heapSort(int data[]) {
 
    int len = data.length;
    for (int i = len / 2 - 1; i >= 0; i--) { 
      maxHeap(data, i, len);    
    }
    for (int i = len - 1; i > 0; i--) {
      int temp = data[0];
      data[0] = data[i];
      data[i] = temp;
      maxHeap(data, 0, i);
    }
  }
 
}