通俗易懂的讲解堆排序(含Gif图)_堆排序删除算法动图

堆的定义

堆排序是一种树形结构选择排序方法，其特点是：在排序过程中，将序列视为一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的关系，在当前无序区间中选择关键字最大(或最小)的元素。堆的定义如下：

n 个关键字序列 L[1,2,3...n] 称为堆，当且仅当该序列满足：

① L(i) <= L(2i) 且 L(i) <= L(2i+1)         ② L(i) >= L(2i) 且 L(i) >= L(2i+1)                   (1 <= i <= ⎿n/2⏌)

满足第一种情况的堆称为小根堆(或小顶堆)，满足第二种情况的堆称为大根堆(大顶堆)。在大根堆中，最大的元素存放在根结点中。对其任一非根结点，它的值小于等于其父亲结点的值。小根堆的定义刚好相反，根结点是最小元素。建立一个堆有两种方法，很多书籍把这两种方法称为向上调整和向下调整：

向下调整是让调整的结点与其孩子结点进行比较。
向上调整是让调整的结点与其父亲结点进行比较。

 

向上调整

向上调整需要从根结点开始建堆(以小根堆为例)，基本思路：每添加一个元素，将该元素与其父结点进行比较，若新增结点小于父结点，则交换两个结点的值，然后继续与上一级的父结点进行比较。停止向上调整的条件是该结点大于父结点的值。现有序列 list [ ] = {87, 45, 78, 32, 17, 65, 53, 9} 分别用向上调整和向下调整进行建堆，看看这两种方法有什么区别。

向上调整建堆的过程：

添加元素 9 的向上调整 gif：

向上调整代码：

void AdjustUp(int a[],int size)
{                                //size是数组目前的大小
    int temp,flag=0;
    if(size==1)
        return;                  //此时是堆顶，不需要上调
    while(size!=1 && flag==0)    
    {
        if(a[size] < a[size/2])  //与父结点进行对比
        {
            temp = a[size];
            a[size] = a[size/2];
            a[size/2] = temp;
        }
        else
        {
            flag = 1;
        }
        size = size/2;           //更新编号i为它父结点的编号。
    }
}
 
void AdjustUp1(int a[], int k)
{//参数k为向上调整的结点，也是堆的元素个数
	if(k == 1)
		return;
	a[0] = a[k];
	int i = k/2;
	while(i > 0 && a[i] > a[0])  //若结点值小于父结点，则将父结点向下调
	{
		a[k] = a[i];              //父节点向下调
		k = i;
		i = k/2;                  //继续向上比较
	}
	a[k] = a[0];
}

 

向下调整

向下调整建堆是一个反复筛查的过程。n 个结点的完全二叉树，最后一个结点是第⎿n/2⏌个结点的孩子(完全二叉树的性质)。对第⎿n/2⏌个结点为根的子树筛查(对于小根堆，若结点的关键字大于左右孩子中关键字较小者，则交换)，使该子树成为堆。之后向前依次对各结点(⎿n/2⏌-1 ～ 1)为根的子树进行筛选，看该结点值是否小于其左右子结点的值，若不小于，则将左右子结点中的较小值与之交换，交换后可能会破坏下一级的堆，于是继续采取上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整方法建堆，直到根结点。根据原始数据建立的树形结构如下：

根据向下调整的思路，从第 4 个结点开始进行筛查建立小根堆：

向下调调整思路：将该结点与其孩子结点进行比较，选取其中最小进行交换，若该节点本身就是最小的结点，则不需要进行交换操作。如上图，需要将 9 和 32 进行交换。然后对第 3 个结点进行调整，该过程较为简单，所以省略。接下来展示第 2 个结点的调整情况。

对第 2 个结点进行调整时，需要交换 9 和 45。但是交换后发现 32 比 45 要小，所以还需要进行一次交换操作。该过程告诉我们，在交换父子结点后，子结点的堆属性可能被破坏，所以要对子结点进行调整(直至子结点为叶子结点为止)。以下是第 2 个结点最终的调整情况：

向下调整的最终形态：

向下调整 gif：

向下调整代码：

void heap_ajust_min(int *b, int i, int size)  //a为数组，size为堆的大小
{
    int lchild = 2*i;        //i的左孩子节点序号 
    int rchild = 2*i +1;     //i的右孩子节点序号 
    int min = i;             //记录根和左右子树中最小的数的下标
	int temp;
    if(i <= size/2)          //调整不需要从叶结点开始
    {
        if(lchild<=size && b[lchild]<b[min])
        {
            min = lchild;
        }    
        if(rchild<=size && b[rchild]<b[min])
        {
            min = rchild;
        }                    //两个if语句寻找三个结点中最小的数
        if(min != i)         //如果min不等于i，说明最小的值在左右子树中
        {
            temp = b[i];     //交换a[i]和a[min]的值
            b[i] = b[min];
            b[min] = temp;
            heap_ajust_min(b, min, size); //被交换的子树可能不满足堆的定义，需要对被交换的子树重新调整
        }
    }        
}
 
 
void build_heap_min(int *b, int size)      //建立小根堆 
{
    int i;
    for(i = size/2; i >= 1; i--)           //非叶子节点最大序号值为size/2，从这个结点开始调整
    {                                      //注意for中的循环条件(i = size/2; i >= 1; i--)
        heap_ajust_min(b, i, size);         
    }    
}

向下调整的时间与树的高度有关，为 O(h)。建堆过程中每次向下调整时，大部分结点的高度都比较小。我们很容易会发现向上调整和向下调整的最终结果有所不同，但都满足了小根堆的性质。向上调整和向下调整都能够完成建立堆的工作。区别在于，使用向上调整建堆需要从第一个元素开始，过程相当于每次插入一个元素，然后再进行向上调整的工作。向下调整充分的利用了完全二叉树的性质，从⎿n/2⏌结点到根结点逐一筛查。它们的具体操作如下：

for(k = 1; k < size ; ++k)     //向上调整建堆
{
    AdjustUp(b, k);
}
 
for(i = size/2; i >= 1; i--)   //向下调整建堆      
{
    heap_ajust_min(b, i, size); 
}    

 

堆排序

应用堆进行排序的思路很简单：首先将存放在 L[1,2,3...n] 中的 n 个元素建成初始堆，由于堆本身的特点，堆顶元素就是最值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点不满足堆的性质，经过向下调整后使其恢复堆的性质，再输出堆顶元素。重复操作，直至最后一个元素为止。

堆排序代码：

void heap_sort_min(int *a, int size)
{
    int i;
	int temp;
    for(i = size; i >= 1; i--)
    {
        temp = a[1];
        a[1] = a[i];
        a[i] = temp;               //交换堆顶和最后一个元素
        heap_ajust_min(a, 1, i-1); //再一次调整堆顶节点成为小顶堆
    }
} 

利用上述小根堆代码完成排序，会发现序列是倒序的，这是因为排序过程是从后往前不断调整小根堆的结果。如果想要获得升序序列，需要使用大根堆进行排序。

堆支持删除和插入操作，删除元素时，需要将最后一个元素放到堆顶，然后使用向下调整，使堆保持堆的特性。对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点进行向上调整操作。注意：插入元素时(小根堆为例)，只需要调用一次向上调整函数便能恢复堆的属性。因为在插入之前，堆本身是完整的。此时若插入元素小于父结点的值，那么只需要交换两个结点而不需要考虑别的情况。这是因为之前满足堆性质，而插入了一个更小的值，交换后堆属性不变。具体可以看添加 9 的时候的 gif。可以根据需求，将向上调整和向下调整搭配着使用。例如：小根堆删除元素后使用向下调整恢复堆的性质。

完整代码：

#include<stdio.h>
#include<math.h>
 
void heap_ajust_min(int *b, int i, int size)  /*a为堆存储数组，size为堆的大小*/
{
    int lchild = 2*i;       //i的左孩子节点序号 
    int rchild = 2*i +1;     //i的右孩子节点序号 
    int min = i; /*存放三个顶点中最大的数的下标*/
	int temp;
    if(i <= size/2)          //假设i是叶节点就不用进行调整 
    {
        if(lchild<=size && b[lchild]<b[min])
        {
            min = lchild;
        }    
        if(rchild<=size && b[rchild]<b[min])
        {
            min = rchild;
        }
        if(min != i)
        {
            temp = b[i]; /*交换a[i]和a[max]的值*/
			b[i] = b[min];
			b[min] = temp;
            heap_ajust_min(b, min, size); /*被交换的位置曾经是大根堆，如今可能不是大根堆
			                            所以须要又一次调整使其成为大根堆结构*/ 
        }
    }        
}
 
void build_bheap_min(int *b, int size) //建立小堆
{
    int i;
    for(i=size/2; i >= 1; i--)      //非叶节点最大序号值为size/2
    {
        heap_ajust_min(b, i, size); 
    }    
}
 
void heap_sort_min(int *a, int size)
{
    int i;
	int temp;
    for(i = size; i >= 1; i--)
    {
        temp = a[1];
		a[1] = a[i];
		a[i] = temp;               //交换堆顶和最后一个元素
        heap_ajust_min(a, 1, i-1); //再一次调整堆顶节点成为小顶堆
    }
} 
 
void AdjustUp(int a[],int size)
{
    int temp,flag=0;
    int k;
    if(size==1)
        return;//此时是堆顶，不需要上调
    while(size!=1 && flag==0)
    {
        if(a[size] < a[size/2])
        {
            temp = a[size];
            a[size] = a[size/2];
            a[size/2] = temp;
        }
        else
        {
            flag = 1;
        }
        size = size/2;//更新编号i为它父结点的编号。
    }
}
 
void AdjustUp1(int a[], int k)
{//参数k为向上调整的结点，也是堆的元素个数
	if(k == 1)
		return;
	a[0] = a[k];
	int i = k/2;
	while(i > 0 && a[i] > a[0])  //若结点值小于父结点，则将父结点向下调
	{
		a[k] = a[i];              //父节点向下调
		k = i;
		i = k/2;                  //继续向上比较
	}
	a[k] = a[0];
}
 
int main(int argc, char *argv[])
{   
	int i,j,k;
	int count=1;
	int a[]={0, 87, 45, 78, 32, 17, 65, 53, 9};
	int b[]={0, 87, 45, 78, 32, 17, 65, 53, 9};
	int size = sizeof(a)/sizeof(int) -1;
	build_bheap_min(a, size);
	printf("向下调整建立小顶堆:\n"); 
    count=1;
	for(i=0;i<=4;i++)
	{
		for(j=0;j<pow(2,i);j++)
		{
			if(count<=size)
			{
				printf("%d ",a[count++]);
			}else{
				break;
			}
		}
		printf("\n");
	}
 
 
	for(k = 1; k < 9 ; ++k)
	{
		AdjustUp(b, k);
	}
 
	printf("向上调整小顶堆:\n"); 
    count=1;
	for(i=0;i<=4;i++)
	{
		for(j=0;j<pow(2,i);j++)
		{
			if(count<=size)
			{
				printf("%d ",b[count++]);
			}else{
				break;
			}
		}
		printf("\n");
	}
    return 0;
}