堆排序

堆排序是一种利用堆的性质进行的排序算法。所以学习堆排序之前先来简单介绍下堆。

堆

堆数据结构是一种数组对象，如图一所示，它可以被视为一颗完全二叉树。

图一

树中的每个结点与数组中存放该结点值的那个元素对应。树的每一层都是填满的，最后一层可能除外。如果树的结点

和数组的下标都从0开始，那么给定了某个结点的下标i，其父节点PARENT(i)、左儿子LEFT(i)和右儿子RIGHT(i)的下

标可以简单的计算出来：

PARENT(i) = (i - 1) / 2；注：右边的结果取整数部分

LEFT(i) = 2 * i + 1;

RIGHT(i) = 2 * (i + 1)；

最大堆和最小堆

这是堆排序中要用到的两种堆，它们的结点内的数值都要满足堆特性，其细节则由堆的种类而定。在最大堆中，最大

堆特性是指除了根意外的每个结点i，有a[PARENT(i)] >= a[i]，即某个结点的值至多是和其父节点的值一样大。这样，

堆中的最大元素就存放在根结点中；并且，在以某一个结点为根的子树中，各结点的值都不大于该子树根节点的值。

最小堆的组织方式则刚好相反。在堆排序算法中，我们一般使用的是最大堆。

堆排序思想

1.将输入的数组构造出一个最大堆，并求出堆的大小heap_size = n

2.将堆顶元素a[0]和最后一个元素a[heap_size - 1]交换

3.堆的大小减小1，即heap_size = heap_size - 1

4.因为调整了堆的大小和交换了元素，所以新的堆可能不满足最大堆的特性，所以对新的堆进行调整，使其再次满足

最大堆的特性。实现这个调整的函数为：max_heapify

5.重复步骤2、3、4，直到堆只剩下最后一个元素

实现代码

  1 #include<iostream>
  2 using namespace std;
  3 /*
  4 PARENT(i) = (i - 1) / 2；注：右边的结果取整数部分
  5 LEFT(i) = 2 * i + 1;
  6 RIGHT(i) = 2 * (i + 1)；
  7 */
  8 int heap_size;
  9 
 10 inline int LEFT (int i)
 11 {
 12     return 2 * i + 1;
 13 }
 14 
 15 inline int RIGHT (int i)
 16 {
 17     return 2 * (i + 1);
 18 }
 19 
 20 void display (int a[], int n);
 21 void swap (int& n, int& m);
 22 void max_heapify (int a[], int i);
 23 void bulid_max_heap (int a[], int n);
 24 void heap_sort (int a[], int n);
 25 
 26 int main()
 27 {
 28     int a[100];
 29     int n;
 30     while (cin >> n) //只要输入类型和n匹配，那么cin就返回真，while循环就会一直继续下去
 31     {
 32         for (int i = 0; i < n; i++)
 33             cin >> a[i];
 34         heap_sort (a, n);
 35         //display (a, n);
 36     }
 37     return 0;
 38 }
 39 
 40 void display (int a[], int n)
 41 {
 42     for (int i = 0; i < n; i++)
 43         cout << a[i] << " ";
 44     cout << endl;
 45 }
 46 
 47 void swap (int& n, int& m)
 48 {
 49     int temp;
 50     temp = n;
 51     n = m;
 52     m = temp;
 53 }
 54 /*
 55  如果是C++，以传引用的方式,
 56  就像你图片里面写的那样，
 57   在swap 函数中如果m、n的值改变了，
 58   调用 swap 函数时传入的实际参数 a、b的值也是会和m、n一样变化的，
 59   这时可以近似的认为 操作m、 n 实际就是操作a、b。
 60 */
 61 
 62 void max_heapify (int a[], int i)
 63 {
 64     int l = LEFT (i);
 65     int r = RIGHT (i);
 66     int largest;
 67 
 68     if ((l < heap_size) && a[l] > a[i])
 69         largest = l;
 70     else
 71         largest = i;
 72 
 73     if ((r < heap_size) && a[r] > a[largest])
 74         largest = r;
 75 
 76     if (largest != i)
 77     {
 78         swap (a[largest], a[i]);
 79         max_heapify (a, largest);
 80     }
 81 }
 82 
 83 void build_max_heap (int a[], int n)
 84 {
 85     heap_size = n;
 86     for (int i = (n - 1) / 2; i >= 0; i--) //父节点下标最大值,依次以每个结点建立最大堆
 87         max_heapify (a, i);
 88 }
 89 
 90 void heap_sort (int a[], int n)
 91 {
 92     build_max_heap (a, n);
 93     
 94     
 95     for (int i = n - 1; i >= 1; i--)
 96     {
 97         swap (a[i], a[0]);//a[n-1]变成最大值
 98         heap_size--;
 99         max_heapify (a, 0);
100     }
101 
102 }