堆排序
程序员文章站
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);
}
}