算法导论的C实现——堆排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法导论的C实现——堆排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5966字，纯文字阅读大概需要9分钟。

内容图文

算法导论的C实现——堆排序

• 堆
• 最大堆
• 维护最大堆
• 原理
• 代码实现
• 结构体定义
• 交换函数
• MAX_HEAPIFY
• 测试
• 建堆
• 原理
• 代码实现
• 测试
• 排序
• 原理
• 代码实现
• 测试

堆

同二叉树一样，二叉堆并不是什么具有独特结构的新的数据结构。要记住的是心中有堆–二叉堆数据存放时本质还是一个数组，不过从另一个角度来看的话，它是一个近似的二叉完全树，树中的每一个节点对应数组中的一个元素。下图就是堆的最显然的解释。

最大堆

在定义最大堆之前，需要计算出父结点，左孩子和右孩子：
$PARENT(i) = \lfloor x/2 \rfloor$PARENT(i)=?x/2?
$LEFT(i) = 2i$LEFT(i)=2i
$PARENT(i) = 2i+1$PARENT(i)=2i+1
为了方便数组元素的书写，和书中不同的是我采用从0开始计数。虽然后面证实还是和书中采用一样的计数方式要简单一点，不过在堆排序中我还是用的从0开始。代码可以对其进行定义：

#define PARENT(i) static_cast<uint32_t>(floor(i+1/2))
#define LEFT(i) ((i+1)<<1)-1
#define RIGHT(i) (i+1)<<1

最大堆的意思是指，对于每一个结点，其两个子节点均小于它：
$\forall i,A[i]>=A[LEFT(i)] \& A[i]>=A[RIGHT(i)]$?i,A[i]>=A[LEFT(i)]&A[i]>=A[RIGHT(i)]

维护最大堆

原理

MAX-HEAPIFY是用来维护最大堆的最重要的性质，以后对二叉堆的每一类操作都会用到它。
维护最大堆的伪代码如下：

MAX-HEAPIFY(A, i)

	l = LEFT(i)
	r = RIGHT(i)
	if l<=A.heap-size and A[l]>A[i]
		largest = l
	if r<=A.heap-size and A[r]>A[largest]
		largest = r
	else 
		largest = i
	if i!=largest
		swap(A[i], A[largest])
		MAX-HEAPIFY(A, largest)

其实上述过程就是将结点$i$i的值换为此结点和其两个孩子结点中最大的一个，如果交换后子结点违反了最大堆的性质，则进行递归维护。

代码实现

结构体定义

因为C只有一个返回值，所以首先一个二叉堆的结构体作为传入参数和返回值：

//------------------------- max haepify -------------------------//
//STRUCTURE
typedef struct HEAP{
    uint32_t heap_size;
    uint32_t array_size;
    int *Array;
}HEAP;

heap_size和array_size的区别在于，数组中只有部分元素会参与二叉树的构成中。

交换函数

要注意的是，C函数的传参如果不是指针类型，子函数会复制传入的参数，等于另开辟一块内存空间进行操作。这样只会对复制产生的变量进行操作，主函数中定义的变量并不会改变。所以如果要交换主函数变量中的两个数，只能通过传入指针变量的方式进行：

//SWAP two elements
void SWAP(int *a, int *b)
{
    int tempInt = 0;
    int *temp = &tempInt;
    *temp = *a;
    *a = *b;
    *b = *temp;
}

MAX_HEAPIFY

维护最大堆性质的函数如下：

//MAX_HEAPIFY
void MAX_HEAPIFY(HEAP *A, uint32_t i)
{
    uint32_t l = LEFT(i);
    uint32_t r = RIGHT(i);
    uint32_t largest;
    if(l<A->heap_size && A->Array[l]>A->Array[i])
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if(r<A->heap_size && A->Array[r]>A->Array[largest])
    {
        largest = r;
    }
    if(largest != i)
    {
        SWAP(&A->Array[i], &A->Array[largest]);
        MAX_HEAPIFY(A, largest);
    }
}

测试

可以用如下的测试函数最维护最大堆进行测试：

#define ARRAY_SIZE 14
//------------------------- max haepify -------------------------//
void testMAX_HEAPIFY()
{
    //6.2.1
    uint32_t heap_size = ARRAY_SIZE;
    int testArray[ARRAY_SIZE] = {27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0};
    HEAP test = {heap_size, ARRAY_SIZE, testArray};

    drawBINTREE(testArray, test.heap_size);
    printf("\n");

    MAX_HEAPIFY(&test, 2);
    drawBINTREE(testArray, test.heap_size);
    printf("\n");
}

输出结果如下：

The height of this tree is: 4
                            27
            17                              *3*
    16              13              10              1
5       7       12      4       8       9       0

The height of this tree is: 4
                            27
            17                              10
    16              13              9               1
5       7       12      4       8       *3*       0

可以看出3这个结点的左孩子大于它，所以堆维护使将其与10交换。交换完成后，它的孩子结点8和9均大于它，此时选择较大的9再与之交换。
上面用到了画二叉树的工具，具体可以看我博客：算法导论的C实现——画出二叉树。

建堆

实现了维护最大堆之后，就可以将任一个数组构建成最大堆。

原理

首先可以证明子数组$A(\lfloor n/2 \rfloor+1, n)$A(?n/2?+1,n)中的元素全部是二叉堆的叶结点：
假设树的高度为$h$h，则元素的个数最大为$n_{max} = 2^h-1$nmax?=2h?1，此树的叶结点开始标号为$n_{max}-2^{h-1}+1=2^{h-1}$nmax??2h?1+1=2h?1，将$n$n带入$\lfloor n/2 \rfloor+1$?n/2?+1可以得到$\lfloor (2^h-1)/2 \rfloor+1=2^{h-1}$?(2h?1)/2?+1=2h?1。
因为叶结点没有子结点，所以只需要对树中的其它结点进行最大堆维护就可以得到最大堆：

BUILD-MAX-HEAP

	A.heap-size = A.array-size
	for i = floor(A.heap-size/2) downto 1
		MAX-HEAPIFY(A, i)

代码实现

void BUILD_MAX_HEAP(HEAP *A)
{
    for(int iBuild=half_FLOOR(A->heap_size); iBuild>=0; iBuild--)
    {
        MAX_HEAPIFY(A, (uint32_t)iBuild);
    }
}

测试

可以用如下的函数进行测试：

//------------------------- bulid max heap -------------------------//
//TEST FUNCTION
void testBUILD_MAX_HEAP()
{
    int testArray[9] = {5, 3, 17, 10, 84, 19, 6, 22, 9};
    uint32_t array_size = 9;
    HEAP A = {9, array_size, testArray};
    drawBINTREE(A.Array, A.heap_size);

    BUILD_MAX_HEAP(&A);
    drawBINTREE(A.Array, A.heap_size);
}

测试得到的结果如下所示：

The height of this tree is: 4
                            5
            3                               17
    10              84              19              6
22      9
The height of this tree is: 4
                            84
            22                              19
    10              3               17              6
5       9

排序

原理

注意到最大堆有一个性质，就是根结点是堆中最大的树。这样来看的话，一个数组的排序就很简单了。只要不断取出根结点的数，并且保证取出后该树还是最大堆，依次迭代，数组的排序就能完成了。
HEAP-SORT

	BUILD-MAX-HEAP(A)
	for i = A.array-size downto 2
		swap(A[1], A[i])
		A.heap-size-1
		MAX-HEAPIFY(A, 1)

代码实现

//HEAP_SORT
int * HEAP_SORT(HEAP *A)
{
    BUILD_MAX_HEAP(A);
    for(int iHeapsort=A->array_size; iHeapsort>1; iHeapsort--)
    {
        SWAP(&A->Array[0], &A->Array[iHeapsort-1]);
        A->heap_size--;
        MAX_HEAPIFY(A, 0);
    }
    return A->Array;
}

这里返回值指向排序完成后的数组，也即初始数组。

测试

//------------------------- heap sort -------------------------//
//TEST FUNCTION
void testHEAP_SORT()
{
    //6.4-1
    int testArray[9] = {5, 13, 2, 25, 7, 17, 20, 8, 4};
    uint32_t array_size = 9;
    HEAP A = {9, array_size, testArray};
    //init array
    for(int i=0; i< array_size; i++){printf("%d,", testArray[i]);}
    printf("\n");
    //heap sort
    int *pTemp = HEAP_SORT(&A);
    //sorted array
    for(int i=0; i< array_size; i++){printf("%d,", pTemp[i]);}
}

测试结果如下所示：

5,13,2,25,7,17,20,8,4
2,4,5,7,8,13,17,20,25

可以看到数组已经成功拍完序。

内容总结

以上是互联网集市为您收集整理的算法导论的C实现——堆排序全部内容，希望文章能够帮你解决算法导论的C实现——堆排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---