做磁力网站,贵阳网站推广￥做下拉去118cr,广州pc网站建设,建设银行app下载手机银行目录
一.什么是堆#xff1f;
1.堆
2.堆的储存
二.堆结构的创建
1.头文件的声明#xff1a;
2.向上调整
3.向下调整
4.源码#xff1a;
三.建堆算法
1.向上建堆法
2.向下建堆法
四.堆排序
五.在文件中Top出最小的K个数 一.什么是堆#xff1f;
1.堆 堆就…目录
一.什么是堆
1.堆
2.堆的储存
二.堆结构的创建
1.头文件的声明
2.向上调整
3.向下调整
4.源码
三.建堆算法
1.向上建堆法
2.向下建堆法
四.堆排序
五.在文件中Top出最小的K个数 一.什么是堆
1.堆 堆就是完全二叉树而且是一种特殊的完全二叉树它需要满足每一个父节点都大于子节点称为大堆或每一个父节点都小于子节点称为小堆。而对兄弟节点之间的大小关系并没有要求(为此它并不是有序的)。如下 2.堆的储存 对于完全二叉树有一个更好的储存方法就是用顺序表来储存相比链式储存使用顺序表储存的一个很大的好处在于知道一个结点可以很容易的算出它父结点和子结点的下标还有可以随机访问。 父子结点下标计算公式 左子结点下标 父结点下标*21 右子结点下标 父结点下标*22 父结点下标 (子结点下标-1) / 2
二.堆结构的创建
1.头文件的声明
Heap.h
#pragma
#includestdio.h
#includestdlib.h
#includeassert.h
#define HpDataType int
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;int cap;
}Heap;
void HeapInit(Heap* php);//堆的初始化
void HeapDestory(Heap* hp);//堆的销毁
void HeapPush(Heap* hp, HPDataType x);//堆的插入
void HeapPop(Heap* hp);//堆的删除
HPDataType HeapTop(Heap* hp);//取堆顶的数据
int HeapSize(Heap* hp);//堆的数据个数
int HeapEmpty(Heap* hp);//堆的判空void AdjustUP(HpDataType* arr, int child);//向上调整
void AdjustDOWN(HpDataType* arr, int size, int parent);//向下调整
void Swap(HpDataType* a, HpDataType* b);//元素的交换 其中堆的初始化堆的销毁堆的数据个数堆的判空和取堆顶数据和顺序表的操作是一样的这里重点来学一下堆的插入堆的删除。
2.向上调整 插入元素呢直接往数组最后插入就可以但是插入后就不一定是堆结构的所以需要调整。例如一个大堆 向大堆中插入53 调整后 代码示例 void AdjustUP(HpDataType* arr,int child)
{int parent (child - 1) / 2;//计算父节点下标while (child0)//注意这里不能是parent0{if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);//封装一个函数进行交换child parent;//更新子节点parent (child - 1) / 2;//更新父节点}elsebreak;}
} ★如果是小堆只需要把if条件的大于号改为小于号 3.向下调整 要注意删除元素我们删除的不是尾元素这样毫无意义我们删除的是下标为0位置的元素它是整个堆中最小或最大的元素。怎么删除呢直接将它删除然后后面的元素在覆盖上吗这样做的话它就不是堆了而且元素之间关系将会全部混乱就需要从0开始创建堆效率非常低我们可以把首元素与尾元素互换然后删除尾元素虽然这个操作过后它也可能就不是堆了不过我们可以将首元素向下调整让它成为堆。比刚才的方案效率要高得多。 比如我们删除大堆中的一个元素 调整过程 调整后的结果 代码示例 void AdjustDOWN(HpDataType* arr, int size, int parent)
{int child parent * 2 1;while (child size){if ((child1)sizearr[child] arr[child 1])child;if (arr[child] arr[parent]){Swap(arr[parent], arr[child]);parent child;child parent * 2 1;}elsebreak;}
} ★如果是小堆只需要把if条件里兄弟节点的大小关系和父子节点的大小关系改变一下就行 4.源码
#define _CRT_SECURE_NO_WARNINGS 1
#includeHeap.h
void HeapInit(Heap* ps)//初始化
{assert(ps);ps-arr NULL;ps-cap ps-size 0;
}
void HeapDestory(Heap* hp)//销毁堆
{assert(hp);free(hp-arr);hp-cap hp-size 0;
}
void Swap(HpDataType* a, HpDataType* b)//交换元素
{HpDataType c *a;*a *b;*b c;
}
void AdjustUP(HpDataType* arr,int child)//向下调整
{int parent (child - 1) / 2;while (child0){if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
}
void AdjustDOWN(HpDataType* arr, int size, int parent)//向上调整
{int child parent * 2 1;while (child size){if (arr[child] arr[child 1])child;if ((child1)sizearr[child] arr[parent]){Swap(arr[parent], arr[child]);parent child;child parent * 2 1;}elsebreak;}
}
void HeapPush(Heap* ps, HPDataType x)//插入元素
{assert(ps);if (ps-size ps-cap){int pnc ps-cap 0 ? 4 : 2 * ps-cap;HpDataType* pnew realloc(ps-arr, sizeof(HPDataType)*pnc);assert(pnew);ps-arr pnew;ps-cap pnc;}ps-arr[ps-size] x;ps-size;AdjustUP(ps-arr, ps-size - 1);
}
void HeapPop(Heap* hp)//删除元素
{assert(hp);assert(hp-size);if (hp-size 1){hp-size--;return;}Swap((hp-arr[0]), (hp-arr[hp-size - 1]));hp-size--;AdjustDOWN(hp-arr, hp-size, 0);
}
HPDataType HeapTop(Heap* hp)//取堆顶元素
{assert(hp);assert(hp-size);return hp-arr[0];
}
int HeapSize(Heap* hp)//计算堆元素个数
{assert(hp);return hp-size;
}
int HeapEmpty(Heap* hp)//判断堆是否为空
{assert(hp);return hp-size 0;
}
三.建堆算法 在学习建堆算法的时候我们以对数组建堆为例就是把数组的数据之间的关系做成一个堆结构一般有两种方法向上调整建堆和向下调整建堆具体怎么做我们来看下面。
1.向上建堆法 向上建堆法也就是通过向上调整建堆我们拿到一个数组后可以把数组的首元素当做堆第二个元素当做把新的元素插入堆然后通过向上调整构成新的堆以此类推下去把数组遍历完后一个堆就建成了。时间复杂度为O(N*logN)
代码示例
#includestdio.h
#includeHeap.h
int main()
{int arr[] { 1,9,3,7,6,4,2,10,8,5 };int size sizeof(arr) / sizeof(int);for (int i 0; i size; i)AdjustUP(arr, i);//该函数在上文已给出这里不再展示printf(建大堆后\n);for (int i 0; i size; i)printf(%d , arr[i]);return 0;
} 不过该方法相比向下调整建堆效率比较低我们来看向下调整建堆法。
2.向下建堆法 向下建堆法也就是通过向下调整建堆要注意并不是从首元素开始调整因为刚开始它并不满足左右子树都是堆结构所以不能直接从第一个元素开始向下调整。既然要满足左右子树都是堆那么我们可以考虑从最后一个元素开始调整不过最后一层下面已经没有元素了它已经是堆并不用调整那么我们从倒数第二层开始调整所以我们先来计算一下倒数第二层最后一个父节点的下标 (size-1-1)/2 第一个size-1得到二叉树的最后一个元素的下标再减一除以二得到它的父节点的下标。
代码示例
#includestdio.h
#includeHeap.h
int main()
{int arr[] { 1,9,3,7,6,4,2,10,8,5 };int size sizeof(arr) / sizeof(int);for (int i (size - 1 - 1) / 2; i 0; i--)AdjustDOWN(arr, size,i);//该函数在上文已给出这里不再展示printf(建大堆后\n);for (int i 0; i size; i)printf(%d , arr[i]);return 0;
}
它的时间复杂度为O(N)证明如下 其中Sn为总的调整次数. 四.堆排序 给一个数组建堆后利用堆的性质给数组排序使其效率更高这就是一个堆排序。比如现在要对一个数组进行堆排序第一个问题就是建大堆还是小堆怎么利用堆来给数组排序。 要进行升序就需要建大堆如果建的是小堆那么堆顶也就是首元素就是最小的元素并不需要动那么来处理第二个元素就注意到它并不一定是第二小的元素只能从第二个元素开始重新建一个小堆那么每排一个元素都需要重新建一个小堆效率就会变得很低。 升序建大堆的话第一个元素就是最大的元素我们可以让它与最后一个元素互换然后把堆的元素个数减一(就是把最后一个元素当做是堆外)最后把堆顶元素向下调整反复操作直到堆的元素个数变为了零。这样一个数组就按升序排好了。 降序需要建小堆原理和排升序相同这里就不在赘述。
代码示例
#includestdio.h
#includeHeap.h
int main()
{int arr[] { 1,9,3,7,6,4,2,10,8,5 };int size sizeof(arr) / sizeof(int);for (int i (size - 1 - 1) / 2; i 0; i--)AdjustDOWN(arr, size,i);printf(建大堆后\n);for (int i 0; i size; i)printf(%d , arr[i]);while (size){Swap(arr[0], arr[size - 1]);//交换元素size--;AdjustDOWN(arr, size, 0);}printf(\n排序后\n);for (int i 0; i sizeof(arr) / sizeof(int); i)printf(%d , arr[i]);return 0;
}
五.在文件中Top出最小的K个数 用堆结构的一个好处就在于不需要排序就能高效的找出最小的前n个元素或最大的前n个元素现在我们来利用堆来尝试找出文件中最小的K个数一个比较低效的一个方法就是把文件中涉及到的所以数据都取出来然后把它建成一个小堆然后Pop出前k次得到最小的k个数。但是如果这个数据非常的大呢比如有上亿个数据那么就会消耗很大的内存空间。 有一个很优的方法就是只取出文件的前K个数建成一个大堆也就是说这个堆只用储K个元素那么堆顶就是这个堆的最大元素然后继续遍历文件每遍历一个元素都与堆顶元素作比较如果比堆顶元素小就更新一下堆顶元素(把小的那个变成堆顶元素)然后进行向下调整直到遍历完整个文件那么此时堆中的元素就是文件中最小的K个元素。此方法在时间复杂度上与上一方法差不多但它大大的节省了空间。
代码示例
#includestdio.h
#includeHeap.h
void CreateNDate()
{//造数据写入文件中int n 10000;srand((unsigned int)time(NULL));const char* file data.txt;FILE* fin fopen(file, w);if (fin NULL){perror(fopen error);return;}for (int i 0; i n; i){int x rand() % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
}
void PrintTopK(int k)
{int* arr (int*)malloc(sizeof(int) * k);assert(arr);FILE* fop fopen(data.txt, r);if (!fop){perror(fopen error);return;}for (int i 0; i k; i)//先取出k个建大堆fscanf(fop, %d, arr[i]);for (int i (k - 1 - 1) / 2; i 0; i--)AdjustDOWN(arr, k, i);int x 0;while (fscanf(fop, %d, x) ! EOF){if (arr[0] x){arr[0] x;AdjustDOWN(arr, k, 0);}}for (int i 0; i k; i)//输出堆中元素printf(%d , arr[i]);
}
int main()
{CreateNDate();int k 0;scanf(%d, k);PrintTopK(k);return 0;
}
