免费ppt模板素材网站有哪些,常州制作网站,网站建设与网页制作教程,个人app开发平台免费个人主页#xff1a;Lei宝啊
愿所有美好如期而遇 目录
堆的介绍#xff1a;
关于堆的实现及相关的其他问题#xff1a;
堆的初始化#xff1a;
堆的销毁#xff1a;
插入建堆#xff1a;
堆向上调整#xff1a;
交换两个节点的值#xff1a;
堆向下调整Lei宝啊
愿所有美好如期而遇 目录
堆的介绍
关于堆的实现及相关的其他问题
堆的初始化
堆的销毁
插入建堆
堆向上调整
交换两个节点的值
堆向下调整
删除根节点
求堆顶数据
打印堆的每一个节点的值
堆排序
堆的节点数量
判断堆是否为空
创建一个多数据文件
TopK问题(综合)
向上/向下调整建堆哪个时间复杂度更优秀 堆的介绍 首先堆是不完全二叉树。 不完全二叉树除了最后一层外其他层每一层都是满的最后一层节点从左到右排。 再者堆分为大堆和小堆。 大堆父母节点的值大于等于孩子节点 小堆父母节点的值小于等于孩子节点 关于堆的实现及相关的其他问题
我们在主函数中将定义一个Heap hp;
typedef int Heaptype;
typedef struct Heap
{Heaptype* data;int size;int capacity;
}Heap;//堆的初始化
void HeapInit(Heap* php);
//堆的销毁
void HeapDestroy(Heap* php);
//插入建堆
void HeapPush(Heap* php, Heaptype num);
//堆向上调整
void Ajustup(Heaptype* a, int child);
//交换两个节点的值
void Swap(Heaptype* p1, Heaptype* p2);
//堆向下调整
void AjustDown(Heaptype* a, int n, int parent);
//删除根节点
void HeapPop(Heap* php);
//求得堆顶数据
Heaptype HeapTop(Heap* php);
//打印堆的每一个节点的值
void HeapPrint(Heaptype* arr, int size);
//堆排序
void HeapSort(Heaptype* arr, int size);
//堆的节点数量
void HeapSize(Heap* php);
//判读堆是否为空
void HeapEmpty(Heap* php);
//创建一个多数据文件
void CreateNDate();
//TopK问题
void PrintTopK(int k);
堆的初始化
void HeapInit(Heap* php)
{assert(php);php-data NULL;php-size 0;php-capacity 0;
}堆的销毁
void HeapDestroy(Heap* php)
{assert(php);free(php-data);php-data NULL;php-size 0;php-capacity 0;
}
插入建堆
void HeapPush(Heap* php, Heaptype num)
{assert(php);if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;Heaptype* temp (Heaptype*)realloc(php-data, sizeof(Heaptype) * newcapacity);if (temp NULL){perror(realloc fail);printf(\n%s, __LINE__);}php-data temp;php-capacity newcapacity;}php-data[php-size] num;//插入后当即向上调整以保证还是个堆Ajustup(php-data, php-size - 1);
}
堆向上调整
//堆向上调整调整一轮建堆就循环插入去建
void Ajustup(Heaptype* a, int child)
{int parent (child - 1) / 2;//当child 0 的时候parent也为0while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}}
交换两个节点的值 void Swap(Heaptype* p1, Heaptype* p2)
{Heaptype temp *p1;*p1 *p2;*p2 temp;}
堆向下调整
//堆向下调整
void AjustDown(Heaptype* a, int n, int parent)
{//从叶子节点开始int child parent * 2 1;while (child n){//找出最小孩子if (child 1 n a[child] a[child 1]){child;}else{if (a[parent] a[child]){Swap(a[child], a[parent]);parent child;child parent * 2 1;} else{break;}}}}
删除根节点
void HeapPop(Heap* php)
{assert(php);assert(php-size 0);Swap(php-data[0], php-data[php-size - 1]);AjustDown(php-data, php-size - 1, 0);php-size--;
}
求堆顶数据
Heaptype HeapTop(Heap* php)
{assert(php);return php-data[0];
}
打印堆的每一个节点的值
void HeapPrint(Heaptype* arr, int size)
{assert(arr);for (int i 0; i size; i){printf(%d , arr[i]);}
}
堆排序
void HeapSort(Heaptype* arr, int size)
{assert(arr);//向上调整建堆(小堆)/*int num size;for (int i 0; i num; i){Ajustup(arr, i);}*///向下调整建堆int last (size - 1 - 1) / 2;for (int i last; i 0; i--){AjustDown(arr, size, i);}//排序int end size - 1;while (end 0){Swap(arr[0], arr[end]);AjustDown(arr, end, 0);end--;}
}
堆的节点数量
void HeapSize(Heap* php)
{assert(php);return php-size;
}
判断堆是否为空
void HeapEmpty(Heap* php)
{assert(php);return php-size 0;
}
创建一个多数据文件
void CreateNDate()
{int n 10000;srand((unsigned int)time(NULL));const char* file heap.txt;FILE* pf fopen(file, w);{if (pf NULL){perror(fopen fail);return;}}for (int i 0; i n; i){int num rand() % 1000000;fprintf(pf, %d\n, num);}fclose(pf);}TopK问题(综合)
void PrintTopK(int k)
{Heaptype* arr (Heaptype*)malloc(sizeof(Heaptype) * k); if (arr NULL){perror(malloc fail);return;}FILE* pf fopen(heap.txt, r);if (pf NULL){perror(fopen fail);return;}for (int i 0; i k; i){fscanf(pf, %d, arr[i]);}//调整为小堆int n (k - 1 - 1) / 2;for (int i n; i 0; i--){AjustDown(arr, k, i);}//由于我们建1的是大小为k的堆堆顶的数值最小当新的数据大于堆//顶时进堆而堆顶的数据被替换之后堆向下调整int a 0;while (fscanf(pf, %d, a) ! EOF){if (a arr[0]){arr[0] a;AjustDown(arr, k, 0);}}//此时堆里的数据是最大的k个数 for (int i 0; i k; i){printf(%d , arr[i]);}fclose(pf);free(arr);
}
向上/向下调整建堆哪个时间复杂度更优秀
答案是堆向下调整时间复杂度为O(N),堆向上调整时间复杂度为O(N*logN)。
