基础闯关记-堆排序

# 堆排序
堆排序，毫无以为，是在堆的数据结构上进行排序，注意，我们这里谈论的堆是二叉堆。所以首先了解二叉堆，然后在二叉堆的基础上排序是很容易的一件事情。
## 什么是二叉堆
二叉堆的结构就是完全二叉树或者近似完全二叉树。在二叉树的结构上保持一定的有序性就是二叉堆，根据这种有序性的不同，分为`最大堆`和`最小堆`
```
最大堆：任一节点的关键字是其子树所有节点的最大值
最小堆：任一节点的关键字是其子树所有节点的最小值
```
举一个例子，下面这两个都是最大堆

![image](http://note.youdao.com/yws/api/personal/file/WEBaa7a5166dd584a1986eede4562db49fd?method=download&shareKey=c57a576603a7f5c183b711109545f611)

## 二叉堆存储
我们知道，二叉树的存储结构最适合的还是每个节点都是一个具有左右孩子和自身数据的结构体
```
struct Node{
    int data;
    int *left;
    int *right;
}
```
但是，完全二叉树不需要这样表示，完全二叉树可以直接用数组表示，这样更节省空间。在一个完全二叉树中，只要知道一个节点的数组下标（i），就能知道它的父节点（i/2），左孩子（2\*i+1）,右孩子（2\*i+2），比如下图中,字母表示二叉堆中节点数值，底下一条内存条表示二叉堆的实际存储情况。

![image](http://note.youdao.com/yws/api/personal/file/WEBc2bd04c7e12ee20b7fa4364c870cf43c?method=download&shareKey=c3f7430096973f33aac0d62e3215fe08)

二叉堆的存储形式即如上图所示，只不过和满二叉树不同的地方在于，二叉堆的数字是保持一定的大小关系。

## 二叉堆的建立
### 二叉堆建立过程过程
因为最大堆和最小堆的原理是一样的，我们举最大堆的例子。建立二叉堆我们使用的方法是先建立一个满二叉树，在满二叉树的基础上我们不断的调整节点，保证根节点大于其他子节点即可，最后就可以形成一个二叉堆。
建立一个满二叉树很简单，申明一个数字即可
```
int arr[] = {19, 20, 40, 56, 3, 9, 50};
```
这时候形成的二叉树如图所示

![image](http://note.youdao.com/yws/api/personal/file/WEB303e2f42c0c3af70401b31a7c72c7be5?method=download&shareKey=6f0220d7a4d9c5261d4fbe0417f68527)

注意，这个时候的二叉树还不能形成一个二叉堆，因为我们发现最大的数字56不在根节点中。

剩下很关键的步骤，就是不断的调整节点，做法是：首先调整最右边的子树，即只看40,9,50三个元素，根节点40与它的左右孩子9,50对比找出其中的较大者，发现是50，所以50跟40位置互换，这样最右子树就满足二叉堆的条件了。然后这个过程左子树也递归进行，最后就会形成二叉堆。整个递归过程可以用下面的图表示

![image](http://note.youdao.com/yws/api/personal/file/WEB581784747e24497f9e9dcc47e098218f?method=download&shareKey=df909f9171fe8d921bc471c89c916d7d)

注意这个图示中标红的地方，如果根节点和孩子节点发生交换之后，这时候孩子节点又作为子树的根节点了，这是一个新的值，所有又要重新比较，最终保持交换之后的孩子节点依然是所在子树种最大的。

### 二叉堆建立的实现
按照我们上面的流程图，首先调整最右子树，让其符合二叉堆，然后是最左子树调整，最后依次这样递归调用。所以我们定义一个函数`heapify`来维持二叉堆的性质。

然后主流程就是依次调用这个函数来调整整个二叉树，调整完之后arr就是一个二叉堆
```
void buildHeap(int arr[], int length) {
    if (length <= 1){
        return;
    }

int n = (length - 2) / 2;// 从最右子树看是找根节点位置

while (n >= 0) {
        heapify(arr, length, n);//循环调用调整函数，调整每颗子树
        n--;
    }
}

```
接下来，看调整函数的实现
```
/**
 * arr 表示数组
 * length 表示数组长度
 * root 根节点位置
 */
void heapify(int arr[], int length, int root) {
    if (root >= length) {
        return;
    }

int largest = root;//默认最大值是根节点位置
    int left = root * 2 + 1;//根节点对应左孩子
    int right = root * 2 + 2;//根节点对应右孩子

if (left < length && arr[left] > arr[largest]) {
        largest = left;
    }

if (right < length && arr[right] > arr[largest]) {
        largest = right;
    }

if (largest != root) {
        swap(&arr[root], &arr[largest]);//最大值不在根节点，需要交换
        heapify(arr, length, largest);//注意，上图中红线沉底操作，需要再次以largest为节点调整
    }
}

//工具函数，交换两个地址
void swap( int *a, int *b )
{
    int temp = *b;
    *b = *a;
    *a = temp;
}

```

通过上面两个函数，我们可以使用那两个函数建立一个最大堆
```
int main(){
    int arr[] = {3, 1, 5, 6, 7, 2, 4};
    int length = 7;
    buildHeap(arr, length);
    
    return 0;
}
```
二叉堆还有很多其他的操作，插入，删除等等。这里用不到，就不介绍了。
## 基于二叉堆的堆排序
有了二叉堆，堆排序就非常简单了。我们只要根节点取出，就是整个数组中最大的值，然后最后一个元素放入根节点，重新调整剩下的元素，调整好之后再取出根节点，就是第二大的元素......。这里需要注意的一点，在一个二叉堆上取出根节点（也就是第一个元素）后，然后把最后一个元素插入到根节点，这个时候，只需要调整根节点就可以了，因为其他的子树已经符合二叉堆了。总而言之，二叉堆的最大值不断的往后放，二叉堆的长度不断减一，这样最终会形成一个排好序的数组。比如下面找出56这个最大值的过程

![image](http://note.youdao.com/yws/api/personal/file/WEB815199656cac94b96f59ed538a2cf79e?method=download&shareKey=ffeab44b905d825b0e7cb2abbfd31ea2)

具体函数的实现很简单：
```
void heapSort(int arr[], int length){
    buildHeap(arr, length);建立二叉堆
    while(length > 0){
        swap(&arr[0], &arr[length-1]);;//根节点和最后一个节点交换一下
        length --;//长度减一
        heapify(arr, length, 0);//调整剩下的元素，这里调整根节点0就可以，其他的子树符合二叉树性质
    }
}
```
## 堆排序完整示例
```
#include<stdio.h>
void builHeap(int arr[], int length);
void heapify(int arr[], int length, int root);
void swap( int *a, int *b );
void heapSort(int arr[], int length);

int main(){
    int arr[] = {3, 1, 5, 6, 7, 2, 4};
    int length = 7;
    heapSort(arr, length);
    int i;
    for(i=0; i<7; i++){
        printf("%d ",arr[i]);
    }  
    return 0;
}

//在数组的基础上建立二叉堆
void buildHeap(int arr[], int length) {
    if (length <= 1){
        return;
    }

int n = (length - 2) / 2;// 从最右子树看是找根节点位置

while (n >= 0) {
        heapify(arr, length, n);//循环调用调整函数，调整每颗子树
        n--;
    }
}
/**
 * 以一个根节点为基准，不断调整二叉树至二叉堆
 * arr 表示数组
 * length 表示数组长度
 * root 根节点位置
 */
void heapify(int arr[], int length, int root) {
    if (root >= length) {
        return;
    }

int largest = root;//默认最大值是根节点位置
    int left = root * 2 + 1;//根节点对应左孩子
    int right = root * 2 + 2;//根节点对应右孩子

if (left < length && arr[left] > arr[largest]) {
        largest = left;
    }

if (right < length && arr[right] > arr[largest]) {
        largest = right;
    }

//工具函数，交换两个元素
void swap( int *a, int *b )
{
    int temp = *b;
    *b = *a;
    *a = temp;
}

//二叉堆排序实现
void heapSort(int arr[], int length){
    buildHeap(arr, length);
    while(length > 0){
        swap(&arr[0], &arr[length-1]);;//根节点和最后一个节点交换一下
        length --;//长度减一
        heapify(arr, length, 0);//调整剩下的元素
    }
}
```

Navigation

Recent Posts

Friend Links