python做的网站有什么漏洞,2019网站建设,怎么找外包公司,wordpress content slide堆的实现-----C语言版 目录#xff1a;一、堆的实现1.1堆的定义1.2堆的实现1.2.1堆的各个接口1.2.2堆的向上调整1.2.3堆的向下调整1.2.4堆的定义声明和初始化1.2.5堆的数据处理1.2.6堆的判空和堆的数据个数以及堆销毁1.2.7堆的代码实现 二、TOP—K问题 目录#xff1a;
一、… 堆的实现-----C语言版 目录一、堆的实现1.1堆的定义1.2堆的实现1.2.1堆的各个接口1.2.2堆的向上调整1.2.3堆的向下调整1.2.4堆的定义声明和初始化1.2.5堆的数据处理1.2.6堆的判空和堆的数据个数以及堆销毁1.2.7堆的代码实现 二、TOP—K问题 目录
一、堆的实现
1.1堆的定义
堆heap是特殊的数据结构。堆通常是一个可以被看做一棵完全二叉树(逻辑层面上)的数组对象(物理层面上),常用来在一组变化频繁(发生增删查改的频率较高)的数据中寻找最值.将根结点最大的堆叫做最大堆或大根堆这样可以找到堆中的最大值(根节点的值);根结点最小的堆叫做最小堆或小根堆,这样可以找到堆中的最小值。 其中堆不一定是完全二叉树只是为了方便存储和索引我们通常用完全二叉树的形式来表示堆而已。 二叉堆是一个数组它可以被看成是一个近似的完全二叉树。 最大堆最小堆如图 最大堆根结点大于左右子树结点的值左右子树结点的值大于它自己左右子树结点的值一种重复下去最小堆根结点小于左右子树结点的值左右子树结点的值小于它自己左右子树结点的值一种重复下去。 1.2堆的实现
用数组实现一个堆
1.2.1堆的各个接口
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.h
#include assert.h
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;//动态数组int _size;//存储数据的下标int _capacity;//动态数组的容量
}Heap;
//堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataTypeHeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);1.2.2堆的向上调整
//向上调整算法
void HeapJustUp(HPDataType a[], HPDataType child)
{int parsent;parsent (child - 1) / 2;//找到孩子的父亲while (child 0){int tmp 0;if (a[parsent] a[child])//孩子比父亲的值大{tmp a[child];a[child] a[parsent];a[parsent] tmp;}elsebreak;child parsent;parsent (parsent - 1) / 2;//找到孩子的父亲}
}对于向上调整我们把它看做是数组结构逻辑上看做一颗完全二叉树。我们只要将要插入堆的数据通过向上调整就可以把它调整成一个大堆。向上调整算法有一个前提除了要插入的数据其它的数据已经构成了一个大堆这样才能调整。 1.2.3堆的向下调整
void HeapJustDown(Heap* hp)
{//先假设当前待调整结点的左孩子结点存在//并且是待调整结点的左右孩子结点不管右孩子结点存不存在都这样假设中值最大的int parent 0;//根节点int child parent * 2 1;//孩子结点while (child hp-_size){//child1 hp-_size说明右孩子结点确实存在//如果hp-_a[child] hp-_a[child1]也成立那说明左右孩子结点中值最大的是右孩子结点if ((child 1 hp-_size) hp-_a[child] hp-_a[child 1]){child child 1;}//如果a[child]a[parent],则说明父节点比比左右孩子节点的值都要小要置换if (hp-_a[child] hp-_a[parent]){int tmp hp-_a[parent];hp-_a[parent] hp-_a[child];hp-_a[child] tmp;parent child;child child * 2 1;}//如果a[child] a[parent],那就不需要进行调整else{break;}}
}对于向下调整我们把它看成是一个数组结构逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个大堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。 1.2.4堆的定义声明和初始化
1.堆的声明
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;//动态数组int _size;//存储数据的下标int _capacity;//动态数组的容量
}Heap;创建一个构成动态数组的结构体 2.堆的初始化
// 堆的初始化
void HeapInit(Heap* hp)
{hp-_a (HPDataType*)malloc(sizeof(HPDataType) * 4);if (hp-_a 0){printf(malloc is error\n);exit(-1);}hp-_capacity 4;hp-_size 0;
} 开空间进行初始化 1.2.5堆的数据处理
1.堆的插入
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{//数据满了需要扩容if (hp-_capacity hp-_size){HPDataType* tmp (HPDataType*)realloc(hp-_a, sizeof(HPDataType)*hp-_capacity * 2);if (tmp NULL){printf(realloc is error);exit(-1);}hp-_a tmp;hp-_capacity hp-_capacity * 2;}//不需要扩容hp-_a[hp-_size] x;//插入数据然后_size1//一般数据都是放到数组尾得建堆向上调整这里我们建大堆HeapJustUp(hp-_a, hp-_size - 1);
}1.容量不够就扩容 2.扩容足够就插入数据 3.然后向上调整建大堆直到满足堆 2.堆的删除
// 堆的删除从堆顶开始删
void HeapPop(Heap* hp)
{
assert(hp);//断言为空为假的话就报错
assert(!HeapEmpty(hp));//断言如果不是空为真就执行
//首元素的的值与尾元素交换然后删除尾元素
int tmp hp-_a[0];
hp-_a[0] hp-_a[hp-_size - 1];
hp-_a[hp-_size - 1] tmp;
hp-_size--;
//堆顶元素进行向下调整
HeapJustDown(hp);
}1.挪动覆盖删除堆顶元素重新建堆 2.尽量保证关系不变首尾数据交换再删除尾部数据向下调整建堆 3.获取堆顶数据
// 取堆顶的数据
HPDataTypeHeapTop(Heap* hp)
{assert(hp-_a);assert(!HeapEmpty(hp));//断言如果不是空为真就执行return hp-_a[0];
}堆顶数据就是第一个元素 1.2.6堆的判空和堆的数据个数以及堆销毁
1.堆的数据个数
// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp-_size;
}堆的数据个数就是_size的个数 2.堆的判空
// 堆的判空
int HeapEmpty(Heap* hp)
{assert(hp);return hp-_size 0;
}_size为0说明堆为空 3.堆销毁
// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);free(hp-_a);hp-_a NULL;hp-_capacity hp-_size 0;
}开一块空间malloc程序结束之前要释放空间free 1.2.7堆的代码实现
.h头文件声明
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.h
#include assert.h
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;//动态数组int _size;//存储数据的下标int _capacity;//动态数组的容量
}Heap;
//堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataTypeHeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
.c源文件定义
#include Heap.h
// 堆的构建
void HeapInit(Heap* hp)
{hp-_a (HPDataType*)malloc(sizeof(HPDataType) * 4);if (hp-_a 0){printf(malloc is error\n);exit(-1);}hp-_capacity 4;hp-_size 0;
}
//向上调整算法
HeapJustUp(HPDataType a[], HPDataType child)
{int parsent;parsent (child - 1) / 2;//找到孩子的父亲while (child 0){int tmp 0;if (a[parsent] a[child])//孩子比父亲的值大{tmp a[child];a[child] a[parsent];a[parsent] tmp;}elsebreak;child parsent;parsent (parsent - 1) / 2;//找到孩子的父亲}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{//数据满了需要扩容if (hp-_capacity hp-_size){HPDataType* tmp (HPDataType*)realloc(hp-_a, sizeof(HPDataType)*hp-_capacity * 2);if (tmp NULL){printf(realloc is error);exit(-1);}hp-_a tmp;hp-_capacity hp-_capacity * 2;}//不需要扩容hp-_a[hp-_size] x;//插入数据然后_size1//一般数据都是放到数组尾得建堆向上调整这里我们建大堆HeapJustUp(hp-_a, hp-_size - 1);
}
// 堆的判空
int HeapEmpty(Heap* hp)
{assert(hp);return hp-_size 0;
}
//堆顶元素进行向下调整
void HeapJustDown(Heap* hp)
{//先假设当前待调整结点的左孩子结点存在//并且是待调整结点的左右孩子结点不管右孩子结点存不存在都这样假设中值最大的int parent 0;//根节点int child parent * 2 1;//孩子结点while (child hp-_size){//child1 hp-_size说明右孩子结点确实存在//如果hp-_a[child] hp-_a[child1]也成立那说明左右孩子结点中值最大的是右孩子结点if ((child 1 hp-_size) hp-_a[child] hp-_a[child 1]){child child 1;}//如果a[child]a[parent],则说明父节点比比左右孩子节点的值都要小要置换if (hp-_a[child] hp-_a[parent]){int tmp hp-_a[parent];hp-_a[parent] hp-_a[child];hp-_a[child] tmp;parent child;child child * 2 1;}//如果a[child] a[parent],那就不需要进行调整else{break;}}
}
// 堆的删除从堆顶开始删
void HeapPop(Heap* hp)
{
assert(hp);//断言为空为假的话就报错
assert(!HeapEmpty(hp));//断言如果不是空为真就执行
//首元素的的值与尾元素交换然后删除尾元素
int tmp hp-_a[0];
hp-_a[0] hp-_a[hp-_size - 1];
hp-_a[hp-_size - 1] tmp;
hp-_size--;
//堆顶元素进行向下调整
HeapJustDown(hp);
}
// 取堆顶的数据
HPDataTypeHeapTop(Heap* hp)
{assert(hp-_a);assert(!HeapEmpty(hp));//断言如果不是空为真就执行return hp-_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp-_size;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);free(hp-_a);hp-_a NULL;hp-_capacity hp-_size 0;
}.c源文件测试
#include Heap.h
int main()
{Heap hp;HeapInit(hp);//初始化HeapPush(hp, 2);//插入数据HeapPush(hp, 3);HeapPush(hp, 4);HeapPush(hp, 5);HeapPush(hp, 6);HeapPush(hp, 1);HeapPush(hp, 66);HeapPush(hp, 62);HeapPush(hp, 4);HeapPush(hp, 6);HeapPop(hp);//删除数据,从堆顶开始删int tmp HPDataTypeHeapTop(hp);//取堆顶元素// 堆的数据个数int num HeapSize(hp);printf(建大堆栈顶元素为%d,堆的数据个数%d\n, tmp,num);for (int i 0; i num; i)printf(%d , hp._a[i]);HeapDestory(hp);// 堆的销毁return 0;
}二、TOP—K问题
TOP—K问题求数据集合中前k个最大的元素和最小的元素一般情况数据非常大。 如专业前10世界500强游戏中前100的活跃玩家各种榜单等等。 1.用数据集合中前k个元素来建堆 求前k个最大的元素建小堆 求前k个最小的元素建大堆 2.用剩余的N—K个元素依次与堆顶元素来比较根据规则替换堆顶元素N—K个元素依次与堆顶元素比较完成后堆里的K个元素就是所求的最小或者最大的元素。 例子 问题假设1亿个数内存存不下数据在文件中找出最大的前k个数。 1.读取文件的前10个数据在内存数组中建立一个小堆。 2.在依次读取剩下数据跟堆顶元素比较大于堆顶的数据就替换它然后向下调整。 3.所有数据读完堆里面数据就是最大的前10个数。 #define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.h
#include time.h
#define n 100000000
void WeinteData()//写入1亿数据
{FILE* fp fopen(top.txt, w);//打开文件只写
if (fp NULL)
{perror(fopen error);exit(-1);
}
srand((unsigned)time(0));
int arr[100] { 0 };
for (int i 0; i n; i)
{int x rand() % 10000 1;fprintf(fp, %d\n, x);
}
fclose(fp);//关闭文件
}
//两个数交换
void Swap(int* p, int* q)
{int tmp;tmp *q;*q *p;*p tmp;
}
//向下调整算法
void JustDown(int* arr,int k,int parent)
{int child parent * 2 1;//左孩子结点while (child k){if ((child 1 k) arr[child] arr[child 1])//找到最小值的孩子结点child 1;//如果arr[child]arr[parent],则说明父节点比比左右孩子节点的值都要大要置换if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);//让孩子结点为父节点并且更新它的儿子结点parent child;child child * 2 1;}//如果a[child] a[parent],那就不需要进行调整else{break;}}
}
//建小堆
void HeapCreate(int* arr,int k)
{//最后一个结点的父亲结点开始向下调整for (int i (k - 2) / 2; i 0; --i){//向下调整算法JustDown(arr, k, i);}
}
void FileTakeK()
{int k 10;//10个数int* a (int*)malloc(sizeof(int) * k);//开辟一块空间用来建堆if (a NULL){perror(malloc error:);exit(-1);}FILE* file fopen(top.txt, r);//打开top.txt文件,只读模式if (file NULL){perror(fopen error:);exit(-1);}for (int i 0; i k; i){fscanf(file, %d, a[i]);}printf(前10个数:\n);for (int i 0; i k; i)printf(%d , a[i]);//建小堆HeapCreate(a, k);printf(\n建完小堆里面的数:\n);for (int i 0; i k; i)printf(%d , a[i]);//把剩余的n-k个数与小堆的堆顶比较比较完成后堆里的数就是文件里最大的10个数int x 0;while (fscanf(file, %d, x) ! EOF){//比堆顶数大把这个数赋值给堆顶然后向下调整if (x a[0])a[0] x;JustDown(a, k, 0);}printf(\n取最大的10个数:\n);for (int i 0; i k; i)printf(%d , a[i]);free(a);//释放内存fclose(file);//关闭文件
}
int main()
{//写入1亿数据WeinteData();//从文件中取出k个数,建小堆FileTakeK();return 0;
}
