（数据结构）堆
目录
- 一、介绍
- 二、大（小）堆的实现
- 1. 堆的初始化
- 2. 堆的销毁
- 3. 添加元素
- 4. 删除堆顶元素
- 5.取出堆顶元素
- 三、⭐堆排序
- 1.问题
- 2. 思路
- 3. 代码
- 4.🪄 时间复杂度
- 4.1 向下建堆的时间复杂度：
- 4.2 开始排序的时间复杂度：
- 四、🌟TOP-K问题
- 1. 问题
- 2. 思路
- 3. 代码
一、介绍
- 这里的堆，其实是一种数据结构，是将数据按完全二叉树的顺序存储方式存储在一个一维数组中，称为堆
- 如果堆中父节点小于子节点的值，则叫做小堆，其根节点的值是整个堆中最小的
- 如果堆中父节点大于子节点的值，则叫做大堆，其根节点的值是整个堆中最大的
- 堆总是一个完全二叉树，因此操作过程中要保证堆的结构
这就是一个以 9 , 7 , 8 , 6 , 4 , 5 , 3 , 2 , 0 , 1 9,7,8,6,4,5,3,2,0,1 9,7,8,6,4,5,3,2,0,1顺序存储的大堆
二、大（小）堆的实现
typedef int HPDataType;
//堆的数据结构
typedef struct Heap
{
HPDataType* a;
int size;//元素个数
int capacity;//容量
}HP;
1. 堆的初始化
void HeapInit(HP* php)
{
assert(php);//php非NULL
php->a = NULL;
php->size = php->capacity = 0;
}
2. 堆的销毁
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
3. 添加元素
示例：添加10
首先在数组尾添加10，然后在依次向上调整，保证大堆结构。
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//判断扩容
if (php->size == php->capacity)
{
//实现扩容
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newcapacity);
if (tmp == NULL)//扩容失败
{
printf("realloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
//在堆尾（下标为size）处插入x
php->a[php->size] = x;
php->size++;//元素个数加1
//调整堆，使其满足大（小）堆
AdjustUp(php->a, php->size - 1);
}
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
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;
}
}
}
4. 删除堆顶元素
示例：删除10
为了使大堆的结构不乱，不能直接删除根节点10，需要先与尾节点4交互，然后在删除尾结点10，在将根节点4向下调整，保持结构。
void HeapPop(HP* php)
{
assert(php);
//堆中需要有元素
assert(php->size > 0);
//将堆顶和堆尾元素交换
Swap(&(php->a[0]), &(php->a[php->size - 1]));
php->size--;//元素个数减1
//调整堆，使其满足大（小）堆
AdjustDwon(php->a, php->size, 0);
}
只是将元素个数减一，来达到删除的效果，实际上并没删除
void AdjustDwon(HPDataType* a, int size, int parent)
{
//先计算出左孩子的下标
int child = parent * 2 + 1;
//通过size来限定调整的范围
while (child < size)
{
// 选出左右孩子中小/大的那个， '>'是建大堆
if (child+1 < size && a[child+1] > a[child])
{
++child;
}
//如何子节点大于(>)父节点，交换
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
5.取出堆顶元素
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
//即数组中第一个元素
return php->a[0];
}
三、⭐堆排序
1.问题
通过堆的算法，实现对数据排序
2. 思路
- 首先将需要排序的数据，如数组，转化成大（小）堆
- 利用大（小）堆的特点——根节点的值是整个数据中最大（小）的
- 如果是排升序，建立大堆。然后每次把根节点拿出来放到堆尾，这样数据中元素就是由小到大排列了
- 如果是排降序，建立小堆。然后每次把根节点拿出来放到堆尾
3. 代码
void HeapSort(int* a, int n)
{
/*从最后一个节点（下标n-1）的父节点（下标(n-1-1)/2）开始
依次向上（--i）进行向下调整，建立大堆*/
for (int i = (n-1-1)/2; i >= 0; --i)
{
AdjustDwon(a, n, i);
}
int size = n;
while (size > 0)
{
Swap(&a[0], &a[--size]);
//每次从根节点（0），开始每次调整n--个数据的堆。
AdjustDwon(a, size, 0);
}
}
4.🪄 时间复杂度
4.1 向下建堆的时间复杂度：
示例：对有n个节点的堆
则建堆需要交互的次数为：
T
(
n
)
=
2
0
×
(
h
−
1
)
+
2
1
×
(
h
−
2
)
+
2
2
×
(
h
−
3
)
+
.
.
.
+
2
h
−
2
×
1
T(n)=2^0\times(h-1)+2^1\times(h-2)+2^2\times(h-3)+...+2^{h-2}\times1
T(n)=20×(h−1)+21×(h−2)+22×(h−3)+...+2h−2×1
利用错位相减法:
2
∗
T
(
n
)
=
2
1
×
(
h
−
1
)
+
2
2
×
(
h
−
2
)
+
.
.
.
+
2
h
−
2
×
2
+
2
h
−
1
×
1
两式相减
:
T
(
n
)
=
2
1
+
2
2
+
2
3
+
.
.
.
+
2
h
−
1
−
(
h
−
1
)
=
1
+
2
1
+
2
2
+
2
3
+
.
.
.
+
2
h
−
1
−
h
=
1
×
2
h
−
1
2
−
1
−
h
=
2
h
−
1
−
h
2*T(n) = 2^1\times(h-1)+2^2\times(h-2)+...+2^{h-2}\times2+2^{h-1}\times1 \\两式相减:\\ T(n) = 2^1+2^2+2^3+...+2^{h-1}-(h-1)\\ =1+2^1+2^2+2^3+...+2^{h-1}-h\\ =1\times\frac{2^{h}-1}{2-1}-h\\ =2^h-1-h
2∗T(n)=21×(h−1)+22×(h−2)+...+2h−2×2+2h−1×1两式相减:T(n)=21+22+23+...+2h−1−(h−1)=1+21+22+23+...+2h−1−h=1×2−12h−1−h=2h−1−h
其中
n
=
2
h
−
1
h
=
l
o
g
2
(
n
+
1
)
则
T
(
n
)
=
n
−
l
o
g
2
(
n
+
1
)
≈
n
n=2^h-1 \quad h=log_2(n+1)\\则\\T(n) = n-log_2(n+1)\approx n
n=2h−1h=log2(n+1)则T(n)=n−log2(n+1)≈n
4.2 开始排序的时间复杂度：
int size = n;
while (size > 0)
{
Swap(&a[0], &a[--size]);
//每次从根节点（0），开始每次调整n--个数据的堆。
AdjustDwon(a, size, 0);
}
每次交换第一个和最后一个，将数组的个数 − 1 -1 −1，然后将交换上来的根节点向下调整，其最多交换 l o g 2 ( n − 1 ) log_2(n-1) log2(n−1)次(深度)。
循环 n − 1 n-1 n−1次，其时间复杂度大约为 T ( n ) ≈ n × l o g 2 n T(n) \approx n \times log_2n T(n)≈n×log2n
对于整个堆排序，其时间复杂度约为： O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)
四、🌟TOP-K问题
1. 问题
在有n个元素的数据中，找出前
k
k
k个最大（小）的元素（一般n是远大于k的）
2. 思路
这里根据堆，提供三种思路：
-
堆排序，见上文，可以取出排序好的前k个元素
-
建一个 n n n个空间的堆，然后一次取出 k k k次（Top&Pop）
时间复杂度 O ( n + k l o g 2 n ) O(n+klog_2n) O(n+klog2n)，空间复杂度为 O ( n ) O ( n ) O(n)O(n) O(n)O(n). -
先取 k k k个元素，建成大（小）堆，如果是要求前 k k k个最大的元素，建小堆，然后将剩下的元素与堆顶元素进行比较，如果大于堆顶，则替换堆顶元素，然后再调整，到遍历结束，小堆中的 k k k个元素就是整个数据中的前 k k k个最大元素了。
时间复杂度为 O ( k + ( n − k ) l o g 2 k ) O(k+(n-k)log_2k) O(k+(n−k)log2k)，空间复杂度为 O ( k ) O(k) O(k).
3. 代码
对于思路3，代码如下：（需要注意AdjustDwon()，前K个最大的–>建小堆)。
void PrintTopK(int* a, int n, int k)
{
assert(a&&n&&k);
//用a中前k个元素建堆
int* myHeap = (int*)malloc(sizeof(int)*k);
assert(myHeap);
for (int i = 0; i < k; ++i)
{
myHeap[i] = a[i];
}
for (int i = (k - 1 - 1) / 2; i >= 0; --i)
{
AdjustDwon(myHeap, k, i);
}
//将剩余n-k个元素依次与堆顶元素交换，不满则则替换
for (int j = k; j < n; ++j)
{
if (a[j] > myHeap[0])
{
myHeap[0] = a[j];
AdjustDwon(myHeap, k, 0);
}
}
//输出小堆中元素
for (int i = 0; i < k; ++i)
{
printf("%d ", myHeap[i]);
}
printf("\n");
}
🦀🦀观看~