数据结构——堆排序

本文介绍堆排序的思想和代码

基本思想

  • 生成最大堆(heapify)：从倒数第一个非叶节点开始，按照下虑操作找到该节点在最大堆中的位置，逐步遍历每一个非叶结点执行上述操作，生成最大堆
  • 交换最大值到末尾：交换根节点与最后一个元素的值，树节点减少1（刚才根节点是当前树的最大值，更换以后就是有序的元素了，不再参与最大堆调整）
  • 重新生成最大堆（调整根节点）：调整新换上来的根节点（下虑操作），找到其应该在的地方，重新生成最大堆
  • 循环交换根节点和调整根节点这两个步骤，直到最大堆只剩下一个元素

代码实现

  • 堆排序的代码实现 
    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
    // 堆排序实现，对长度为n的数组a进行排序
    void HeapSort(int* a, int n) 
    {
    	// 生成堆 heapify
    	for (int i = n/2-1; i >= 0; --i) // 从n/2-1开始，找到最大的非叶节点
    	{
    		AdjustDown(a, n, i); // 将第i个节点按照下虑操作放置到它在最大堆中应该在的地方，注意本函数执行完后，当前节点i的所有子节点都小于等于节点i，也就是说，在最终生成的最大堆中，节点i的位置不会再更靠后了，详情见后面函数的实现
    	}
    	int end = n - 1; // 用于表示数组尾部结点的下标 数值表示此前数字个数
    	while (end > 0)
    	{
    		Swap(&a[0], &a[end]); // 将根部数据排在最后 达到升序的效果
    		AdjustDown(a, end, 0);
    		--end; // 将从根部换下的值不当作堆中数据 对堆重复以上操作
    	}
    }

    // 最大堆的下虑操作实现：将 数组a的前size个数 所表达的最大堆的 parent节点 通过下虑操作找到其应在的位置
    void AdjustDown(int* a, int size, int parent)//向下调整（O(logn)）
    {
    	// 假设法，假设最大孩子节点是左节点
    	int child = parent * 2 + 1;
    	while (child < size)
    	{
    		// 大堆中 向下调整 找大的孩子节点
    		if (child + 1 < size && a[child] < a[child + 1]) // 假设错误，右孩子大于左孩子
    		{
    			child++; // 更新为右孩子
    		}
    		if (a[child] > a[parent]) // 如果不符合最大堆规则，将父节点与最大的孩子节点进行交换
    		{
    			Swap(&a[child], &a[parent]); // 交换完成
    			// 更新父节点和子节点
    			parent = child; // 此时的父节点变为孩子节点所在位置（还是入参parent对应的那个数字），需要继续进行下一轮最大堆验证
    			child = parent * 2 + 1; // 依然假设法，假设最大孩子节点是左节点
    		}
    		else // 如果满足最大堆规则，终止
    		{
    			break;
    		}
    	}
    }