欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆排序

程序员文章站 2022-06-04 10:38:25
...

一、二叉堆(简称堆)

1、最小堆

  ①二叉堆是一棵完全二叉树

  ②任意子树都是一个二叉堆

  ③任意节点的数据项小于它所有后裔的数据项

  ④任意节点X的父节点的数据项小于X的数据项

堆排序

2、最大堆

与最小堆一样,只不过它的顺序是反过来的。即 任一节点的数据项大于它的所有子节点

                               堆排序

二、实现

二叉堆一般通过"数组"来实现,用数组实现的二叉堆,位置i上的节点跟它的父节点、左右子节点存在一定的规律。为了方便,我们把"二叉堆的第一个元素"放在数组下标为1的位置(也可以放在0的位置)。

①索引为i的左二子的索引为2*i

②索引为i的右二子的索引为2*i + 1

③索引为i的父节点的索引为i / 2

                                   堆排序

                 堆排序

三、保持堆的性质

        我们以最大堆为例,编写一个Keep_MaxHeap函数,该函数输入一个数组A和下标i。假设i的左右子树都是最大堆,但是A[i]可能小于它的儿子,这样就违反了最大堆的性质。
/**
 * n:最大堆中节点个数即数组元素个数
 */
void Keep_MaxHeap(int* A, int i, int n)
{
	int largest;
	int l = 2 * i;     // 左儿子的下标位置
	int r = 2 * i + 1; // 右儿子的下标位置
	int tmp;

	// 计算根节点、左儿子、右儿子中最大值的下标
	if (l<=n && A[i]<A[l])
		largest = l;
	else
		largest = i;

	if (r<=n && A[largest]<A[r])
		largest = r;

	// 如果最大值是根节点,说明已经是最大堆
	if (largest == i)
		return;
	else
	{
		// 交换根节点和最大值,使根节点下移
		tmp = A[i];
		A[i] = A[largest];
		A[largest] = tmp;
	}

	// 根节点下移后子树仍然可能违反最大堆的性质,因此对子树递归调用Keep_MaxHeap
	Keep_MaxHeap(A, largest);
}

三、建堆

        我们自底向上地用Keep_MaxHeap将数组A[1...n]构造成一个最大堆。

子数组A[(n/2 + 1)...n]中的元素都是二叉堆中的叶子节点(文章末尾给出证明),因此可以看作是只含有一个节点的最大堆。编写函数Build_MaxHeap对堆中的其它节点都调用一次Keep_MaxHeap来构造最大堆。

void Build_MaxHeap(int* A, int n)
{
	for (int i=n/2; i>=1; --i)
	{
		Keep_MaxHeap(A, i, n);
	}
}

四、堆排序算法

        开始时,我们先用Build_MaxHeap将输入数组A[1...n]构造成一个最大堆。此时数组中最大的元素在根A[1]处,通过将A[i]和A[n]交换,则数组中最大的元素已经"沉底"。接下来,将数组中的其余元素继续构造最大堆,因为中间元素都没有动过,所以只有根处的元素违背了最大堆性质,因此只需调用Keep_MaxHeap(A,1,n-1)即可。不断重复上述过程,直到堆的大小由n-1减到2排序完成。

void HeapSort(int* A, int n)
{
	int tmp;
	// 第1步:构造最大堆
	Build_MaxHeap(A, n);

	for (int i=n; i>=2; --i)
	{
		// 把最大值(根)沉底
		tmp = *(A + 1);
		*(A + 1) = *(A + i);
		*(A + i) = tmp;
		// 使其余元素继续维持最大堆性质
		Keep_MaxHeap(A, 1, i-1);
	}
}
相关标签: 堆排序