当前位置:网站首页>二叉树(二)——堆的代码实现
二叉树(二)——堆的代码实现
2022-07-05 22:24:00 【雨中春树万人家】
堆用数组实现其物理结构,利用leftchild=2*parent+1以及rightchild=2*parent+2进行父子结点的访问。
堆的基本结构:
typedef int HPDataType;
typedef struct Heap {
HPDataType* a;//动态数组
size_t size;//数据量
size_t capacity;//容量
}HP;
堆的初始化函数:
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
堆的清零函数
void HeapDesTroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;//这一步不要忽略
php->size = php->capacity = 0;
}
堆中添加新元素时,应该:
①保持大根堆(或小根堆)的原有性质不便,即插入新元素后仍然是大根堆(或小根堆)。
②尽量不破坏原有树结构的完整性。
③采用尾插方式,不必大批量挪动数据,以提高效率。
堆中插入新元素的函数(AdjustUp为向上调整函数):
void AdjustUp(HPDataType* a,size_t child)
{
//父子关系计算公式(对于leftchild和rightchild均成立)
size_t parent = (child - 1) / 2;
//可能会持续上调
//此处为小堆,若需要大堆,则只用调整if中的符号就行
while (child>0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//更新关系
child = parent;
parent = (child - 1) / 2;
//注意child=0时,parent=0,会陷入死循环。
//无论用不用size_t,parent始终不会小于0
//-1/2==0
}
//还应该考虑中间就停止的情况
else
{
break;
}
}
}
//插入新数据后,要保持大根堆、小根堆的性质
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//空间不够,先扩容
if (php->capacity == php->size)
{
size_t newCapacity = php->capacity * 2 + 1;
HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc failed.\n");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
//堆中插入数据——向上调整算法
//第一步:先把新数据放在物理结构(顺序表/数组)的尾部
php->a[php->size] = x;
++php->size;
//第二步:向上调整
AdjustUp(php->a, php->size - 1);
}
删除根的函数
void AdjustDown(HPDataType* a,size_t size,size_t root)
{
size_t parent = root;
size_t child = parent * 2 + 1;
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;
}
}
}
//删除堆顶数据(小堆-删除堆顶最小数据/大堆-删除堆顶的最大数据)
//要保持小堆/大堆的性质
//若直接前移剩余数据,则有问题:①破坏结构②时间复杂度为O(N),不方便
//更优秀的方案:第一个数据先和最后一个数据进行对调->不必抹掉数据,直接size--即可->向下调整
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
//第一步:根与最后一个数据进行交换
Swap(&php->a[0], &php->a[php->size-1]);
//第二步:删除数据
--php->size;
//第三步:向下调整
//时间复杂度:O(logN)
AdjustDown(php->a,php->size,0);
}
堆排序函数
//堆排序的步骤比较简单,即:
//将数组中的无序元素全部放到一个新建的堆中,再依次pop出,即得有序的元素列
//堆排序——升序
void HeapSort(HPDataType* a, int size)
{
//第一步:建立一个堆(小堆)
HP hp;
HeapInit(&hp);
//第二步:将数组中的无序数据都放到堆中
//第三步:由于小堆可以依次弹出从小到大的数据,故依次放入数组即可
for (int i = 0; i < size; ++i)
{
HeapPush(&hp, a[i]);
}
size_t j = 0;
while (!HeapEmpty(&hp))
{
a[j] = HeapTop(&hp);
j++;
HeapPop(&hp);
}
HeapDesTroy(&hp);
}
完整代码(含测试用例)
Heap.h
#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap {
HPDataType* a;//动态数组
size_t size;//数据量
size_t capacity;//容量
}HP;
void Swap(HPDataType* pa, HPDataType* pb);
void HeapInit(HP* php);
void HeapDesTroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
void HeapPrint(HP* php);
HPDataType HeapTop(HP* php);
size_t HeapSize(HP* php);
bool HeapEmpty(HP* php);
Heap.c
#include"Heap.h"
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
void HeapDesTroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;//这一步不要忽略
php->size = php->capacity = 0;
}
void Swap(HPDataType* pa, HPDataType* pb)
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
//算法逻辑思想是二叉树,物理上操作的是数组中数据
void AdjustUp(HPDataType* a,size_t child)
{
//父子关系计算公式(对于leftchild和rightchild均成立)
size_t parent = (child - 1) / 2;
//可能会持续上调
//此处为小堆,若需要大堆,则只用调整if中的符号就行
while (child>0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//更新关系
child = parent;
parent = (child - 1) / 2;
//注意child=0时,parent=0,会陷入死循环。
//无论用不用size_t,parent始终不会小于0
//-1/2==0
}
//还应该考虑中间就停止的情况
else
{
break;
}
}
}
//插入新数据后,要保持大根堆、小根堆的性质
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//空间不够,先扩容
if (php->capacity == php->size)
{
size_t newCapacity = php->capacity * 2 + 1;
HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc failed.\n");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
//堆中插入数据——向上调整算法
//第一步:先把新数据放在物理结构(顺序表/数组)的尾部
php->a[php->size] = x;
++php->size;
//第二步:向上调整
AdjustUp(php->a, php->size - 1);
}
void HeapPrint(HP* php)
{
assert(php);
for (size_t i = 0; i < php->size; i++)
{
printf("%d ",php->a[i]);
}
printf("\n");
}
void AdjustDown(HPDataType* a,size_t size,size_t root)
{
size_t parent = root;
size_t child = parent * 2 + 1;
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;
}
}
}
//删除堆顶数据(小堆-删除堆顶最小数据/大堆-删除堆顶的最大数据)
//要保持小堆/大堆的性质
//若直接前移剩余数据,则有问题:①破坏结构②时间复杂度为O(N),不方便
//更优秀的方案:第一个数据先和最后一个数据进行对调->不必抹掉数据,直接size--即可->向下调整
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
//第一步:根与最后一个数据进行交换
Swap(&php->a[0], &php->a[php->size-1]);
//第二步:删除数据
--php->size;
//第三步:向下调整
//时间复杂度:O(logN)
AdjustDown(php->a,php->size,0);
}
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
main.c
#include"Heap.h"
void TestHeap()
{
HP hp;
HeapInit(&hp);
HeapPush(&hp, 1);
HeapPush(&hp, 5);
HeapPush(&hp, 0);
HeapPush(&hp, 8);
HeapPush(&hp, 3);
HeapPush(&hp, 9);
HeapPrint(&hp);
HeapPop(&hp);
HeapPrint(&hp);
HeapDesTroy(&hp);
}
//堆排序的步骤比较简单,即:
//将数组中的无序元素全部放到一个新建的堆中,再依次pop出,即得有序的元素列
//堆排序——升序
void HeapSort(HPDataType* a, int size)
{
//第一步:建立一个堆(小堆)
HP hp;
HeapInit(&hp);
//第二步:将数组中的无序数据都放到堆中
//第三步:由于小堆可以依次弹出从小到大的数据,故依次放入数组即可
for (int i = 0; i < size; ++i)
{
HeapPush(&hp, a[i]);
}
size_t j = 0;
while (!HeapEmpty(&hp))
{
a[j] = HeapTop(&hp);
j++;
HeapPop(&hp);
}
HeapDesTroy(&hp);
}
int main()
{
TestHeap();
HPDataType a[] = { 4,2,7,8,5,1,0,6 };
HeapSort(a, sizeof(a) / sizeof(HPDataType));
for (size_t i = 0; i <= 7; i++)
printf("%d ", a[i]);
return 0;
}
边栏推荐
- The statistics of leetcode simple question is the public string that has appeared once
- Technology cloud report: how many hurdles does the computing power network need to cross?
- 點到直線的距離直線的交點及夾角
- Sentinel production environment practice (I)
- Win11缺少dll文件怎么办?Win11系统找不到dll文件修复方法
- Qtquick3d real time reflection
- boundary IoU 的计算方式
- Type of fault
- Overriding equals() & hashCode() in sub classes … considering super fields
- New 3D particle function in QT 6.3
猜你喜欢
Blocking of concurrency control
Analysis of the problem that the cookie value in PHP contains a plus sign (+) and becomes a space
Kubernetes Administrator certification (CKA) exam notes (IV)
[groovy] groovy dynamic language features (automatic type inference of function arguments in groovy | precautions for function dynamic parameters)
数据泄露怎么办?'华生·K'7招消灭安全威胁
装饰器学习01
Depth first DFS and breadth first BFS -- traversing adjacency tables
Damn, window in ie open()
Talking about MySQL index
Oracle hint understanding
随机推荐
U盘的文件无法删除文件怎么办?Win11无法删除U盘文件解决教程
Comment développer un plug - in d'applet
Win11缺少dll文件怎么办?Win11系统找不到dll文件修复方法
The statistics of leetcode simple question is the public string that has appeared once
1.3 years of work experience, double non naked resignation agency face-to-face experience [already employed]
Advantages and disadvantages of the "Chris Richardson microservice series" microservice architecture
Lightweight dynamic monitorable thread pool based on configuration center - dynamictp
Character conversion PTA
Oracle is sorted by creation time. If the creation time is empty, the record is placed last
Platformio create libopencm3 + FreeRTOS project
Common interview questions of redis factory
Index optimization of performance tuning methodology
[error record] file search strategy in groovy project (src/main/groovy/script.groovy needs to be used in the main function | groovy script directly uses the relative path of code)
The new content of the text component can be added through the tag_ Config set foreground and background colors
Promql demo service
Leetcode simple question: the minimum cost of buying candy at a discount
Hcip day 16
119. Pascal‘s Triangle II. Sol
ESP32 hosted
Solutions for unexplained downtime of MySQL services