目录
- 一、本章重点
- 二、堆
- 2.1堆的介绍（三点）
- 2.2向上调整
- 2.3向下调整
- 2.4建堆（两种方式）
- 三、堆排序
一、本章重点
- 堆
- 向上调整
- 向下调整
- 堆排序
二、堆
2.1堆的介绍（三点）
1.物理结构是数组
2.逻辑结构是完全二叉树
3.大堆:所有的父亲节点都大于等于孩子节点，小堆：所有的父亲节点都小于等于孩子节点。
2.2向上调整
概念：有一个小/大堆，在数组最后插入一个元素，通过向上调整，使得该堆还是小/大堆。
使用条件：数组前n-1个元素构成一个堆。
以大堆为例：
逻辑实现：
将新插入的最后一个元素看做孩子，让它与父亲相比，如果孩子大于父亲，则将它们交换，将父亲看做孩子，在依次比较，直到孩子等于0结束调整·。
如果中途孩子小于父亲，则跳出循环，结束调整。
参考代码：
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])//如果孩子大于父亲，则将它们交换。
{
Swap(&a[child], &a[parent]);
//迭代过程：
child = parent;
parent = (child - 1) / 2;
}
else
{
//如果孩子小于父亲，结束调整
break;
}
}
}
向上调整应用
给大\小堆加入新的元素之后仍使得大\小堆还是大\小堆。
2.3向下调整
概念：根节点的左右子树都是大\小堆，通过向下调整，使得整个完全二叉树都是大\小堆。
使用条件：根节点的左右子树都是大\小堆。
如图根为23，它的左右子树都是大堆，但整颗完全二叉树不是堆，通过向下调整可以使得整颗完全二叉树是堆。
逻辑实现：
选出根的左右孩子较大的那个孩子，然后与根比较，如果比根大，则交换，否则结束调整。
参考代码：
void AdjustDown(HPDataType* a, int size, int root)
{
int parent = root;
int child = parent * 2 + 1;//左孩子
while (child < size)
{
if (child + 1 < size && a[child] < a[child + 1])//如果左孩子小于右孩子，则选右孩子
{
//务必加上child+1，因为当child=size-1时，右孩子下标是size，对其接引用会越界访问。
child++;//右孩子的下标等于左孩子+1
}
if (a[child] > a[parent])//让较大的孩子与父亲比较，如果孩子大于父亲，则将它们交换。
{
Swap(&a[child], &a[parent]);
//迭代过程
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
2.4建堆（两种方式）
第一种：向上调整建堆（时间复杂度是O（N*logN），空间复杂度O（1））
思路是：从第二个数组元素开始到最后一个数组元素依次进行向上调整。
参考代码：
for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}
时间复杂度计算：
以满二叉树进行计算
最坏情况执行步数为：T=(2^1)*1+(2^2)*2+(2^3)*3+….+2^(h-1)*(h-1)
最后化简得：T=2^h*(h-2)+2
又因为(2^h)-1=N
所以h=log(N+1)
带入后得T=(N+1)*(logN-1)+2
因此它的时间复杂度是：O（N*logN）
第二种：向下调整建堆（时间复杂度是O（N），空间复杂度是O（1））
从最后一个非叶子节点（最后一个数组元素的父亲）开始到第一个数组元素依次进行向下调整。
参考代码：
//n代表数组元素个数，j的初始值代表最后一个元素的父亲下标
for (int j = (n - 1 - 1) / 2; j >= 0; j--)
{
AdjustDown(a, n, j);
}
时间复杂度计算：
以满二叉树进行计算
最坏执行次数：
T=2^(h-2)*1+2^(h-3)*2+2^(h-4)*3+…..+2^3*(h-4)+2^2*(h-3)+2^1*(h-2)+2^0*(h-1)
联立2^h-1=N
化简得T=N-log（N+1）
当N很大时，log（N+1）可以忽略。
因此它的时间复杂度是O（N）。
因此我们一般建堆采用向下调整的建堆方式。
三、堆排序
目前最好的排序算法时间复杂度是O（N*logN）
堆排序的时间复杂度是O（N*logN）
堆排序是对堆进行排序，因此当我们对某个数组进行排序时，我们要先将这个数组建成堆，然后进行排序。
首先需要知道的是：
对数组升序，需要将数组建成大堆。
对数组降序，需要将数组建成小堆。
这是为什么呢？
这需要明白大堆和小堆的区别，大堆堆顶是最大数，小堆堆顶是最小数。
当我们首次建堆时，建大堆能够得到第一个最大数，然后可以将它与数组最后的元素进行交换，下一次我们只需要将堆顶的数再次进行向下调整，可以再次将数组变成大堆，然后与数组的倒数第二个元素进行交换，自此已经排好了两个元素，使得它们存储在需要的地方，然后依次进行取数，调整。
而如果是小堆，首次建堆时，我们能够得到最小的数，然后将它放在数组第一个位置，然后你要保持它还是小堆，该怎么办呢？只能从第二个元素开始从下建堆，而建堆的时间复杂度是O（N），你需要不断重建堆，最终堆排序的时间复杂度是O（N*N），这是不明智的。
或者建好小堆后，你这样做:
在开一个n个数组的空间，选出第一个最小数就将它放在新开辟的数组空间中保存，然后删除堆顶数，再通过向下调整堆顶的数，再将新堆顶数放在新数组的第二个位置…….。
虽然这样的时间复杂度是O（N*logN）。
但这样的空间复杂度是O（N）。
也不是最优的堆排序方法。
而建大堆的好处就在它把选出的数放在最后，这样我们就可以对堆顶进行向下调整，使得它还是大堆，而向下调整的时间复杂度是O(logN)，最终堆排序的时间复杂度是O（N*logN）。
堆排序的核心要义：
通过建大堆或者小堆的方式，选出堆中最大或者最小的数，从后往前放。
参考代码：
int end = n - 1;//n代表数组元素的个数
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
整个堆排序的代码：
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(int* a, int n, int root)
{
int child = 2 * root + 1;
while (child < n)
{
if (child + 1 < n && a[child] < a[child+1])
{
child++;
}
if (a[child] > a[root])
{
Swap(&a[child], &a[root]);
root = child;
child = 2 * root + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
//建大堆(向上调整)
//for (int i = 1; i < n; i++)
//{
// AdjustUp(a, i);
//}
//建大堆(向下调整)
for (int j = (n - 1 - 1) / 2; j >= 0; j--)
{
AdjustDown(a, n, j);
}
//升序
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
void printarr(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main()
{
int arr[10] = { 9,2,4,8,6,3,5,1,10 };
int size = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, size);
printarr(arr, size);
return 0;
}
评论(0)