Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说堆排序_基本思想,希望能够帮助你!!!。

二叉堆的定义:二叉堆是完全二叉树或者是近似完全二叉树

二叉堆满足两个特性:

a.父节点的键值总是大于等于或小于等于任何一个子节点的键值

b.每个节点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)

大顶堆:父节点的键值总是大于或等于任何一个子节点的键值

小顶堆:父节点的键值总是小于或等于任何一个子节点的键值

算法思想:堆排序 = 堆构造 + 交换堆末尾元素与根节点 + 删除未节点 + 构造堆 + 交换...一次循环，

由于根节点必定是堆中最大或最小的元素，所以删除出来的元素序列也必定是升序或降序的。

void minHeapFixdown(int arr, int i, int count)
{
	int j, temp;
	temp = arr[i];
	
	j = 2 * i + 1;
	
	while(j < count)
	{
		if (j + 1 < count && arr[j + 1] < arr[j])
		{
			j++; //找出较小的子节点
		}
		
		if(arr[j] >= temp)
		{
			break; //如果较小的子节点比父节点大 直接返回
		}
		
		arr[i] = arr[j]; //设置父节点为较小节点
		i = j; //调整的子节点作为新一轮的父节点
		j = 2 * i + 1; //调整的子节点的子节点
	}
	
	arr[i] = temp;
}

void heapSort(int array[], int count) 
{
    for (int i = (count - 1) / 2; i >= 0; i--) 
	  {
        // 构造小顶堆
        minHeapFixdown(array, i, count);
	  }
 
    for (int i = count - 1; i >= 1; i--) {
 
        // 交换根结点与最末节点
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;
 
        // 剩余的n-1个元素再次建立小顶堆
        minHeapFixdown(array, 0, i);
 
    }
}

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。