深圳住房和城乡建设局网站,租服务器做网站,网站维护需要多久时间,吴江做网站的公司目录
概念#xff1a;
堆的实现
构建
初始化
销毁
插入元素
往上调整
删除堆顶元素
往下调整
返回堆顶元素 返回有效个数
是否为空 堆排序 Top-k问题
编辑 创建数据
堆top-k 概念#xff1a; 堆是将数据按照完全二叉树存储方式存储到一维数组中#xff…
目录
概念
堆的实现
构建
初始化
销毁
插入元素
往上调整
删除堆顶元素
往下调整
返回堆顶元素 返回有效个数
是否为空 堆排序 Top-k问题
编辑 创建数据
堆top-k 概念 堆是将数据按照完全二叉树存储方式存储到一维数组中 堆分为大堆和小堆 大堆父结点大于等于孩子结点 小堆父结点小于等于孩子结点 父结点与左右孩子结点关系 1.父结点 孩子结点-1/2 2.左结点 父结点*21 右结点 父结点*22 堆的实现 堆的逻辑结构是完全二叉树物理结构是一维数组存储 而独特的结点关系堆排序也是一种选择排序 构建
typedef int HPDataType;
typedef struct Heap
{HPDataType* parr;int size; //存储的有效数据个数int capacity; //容量
}Heap;
// 用数组存储
初始化
//堆的初始化
void HeapInit(Heap* php)
{assert(php);php-parr NULL;php-size 0;php-capacity 0;
}
销毁 //堆的销毁
void HeapDestroy(Heap* php)
{assert(php);free(php-parr);php-parr NULL;php-size php-capacity 0;free(php);php NULL;
}
插入元素 因为堆分为两类在数据插入时需要选择适应的调整 以小堆来说当插入一个新元素时插入到堆尾与父结点比较相应的往上调整 //堆的插入元素
void HeapPush(Heap* php, HPDataType x)
{assert(php);//检查容量if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* newparr (HPDataType*)realloc(php-parr, sizeof(HPDataType) * newcapacity);if (newparr NULL){perror(realloc fail);exit(-1);}php-capacity newcapacity;php-parr newparr;}php-parr[php-size] x;php-size;//小堆//向上调整AdjustUp(php-parr, php-size - 1);
}
往上调整 当插入一个新元素按照孩子和父结点之间的关系进行比较交换两结点数据直到满足堆的性质 //向上调整
void AdjustUp(HPDataType* parr,int size)
{int child size;int parent (child - 1) / 2;//小堆 父结点孩子结点while (child0){if (parr[child] parr[parent]){//交换数据Swap(parr[child], parr[parent]);child parent; //更新结点位置parent (child - 1) / 2;}else{break;}}
}
删除堆顶元素 1.将堆顶元素和尾部元素互换位置 2.将此刻不符合规定的堆顶元素往下调整至相应位置 // 删除堆顶根节点
void HeapPop(Heap* php)
{assert(php);//1.堆顶元素和尾部元素置换位置Swap(php-parr[0], php-parr[php-size - 1]);php-size--; //删掉交换后的堆顶元素//2.将新站顶元素找到相应位置//向下调整AdjustDown(php-parr,php-size,0);
}
往下调整 堆顶元素与其孩子结点比较如何找到较大较小的孩子 可以假设法假设较大较小的孩子为左孩子然后验证假设 //向下调整
void AdjustDown(HPDataType* parr,int size,int parent)
{int child (parent * 2) 1;while (childsize) //{//假设左孩子为较小值if (child1size parr[child 1] parr[child]) //验证假设{child; //说明右孩子更小更换孩子位置}//检查是否不符合堆排序结构 if (parr[parent] parr[child]){Swap(parr[parent], parr[child]);//往下更新父结点 孩子结点位置parent child;child parent * 2 1;}else{break;}}
}
返回堆顶元素 起始值为0 //返回堆顶元素
HPDataType HeapTop(Heap* php)
{assert(php);assert(php-size 0);return php-parr[0];
} 返回有效个数 注意构建堆的时候size是最后一个元素的下一个 //返回堆内有效数据个数
size_t HeapSize(Heap* php)
{assert(php);return php-size; //数组下标0开始
}
是否为空
//判断堆是否为空
bool HeapEmpty(Heap* php)
{return php-size 0;
} 堆排序 以上是一些堆的简单功能实现算不上真正的堆排序 假设给定一串数字4,6,2,1,5,8,2,9如何将其排序比如升序 建立一个大堆将堆顶元素与堆尾元素互换且将遍历堆的范围-1保证其想要的值保持不动将此刻不符合规定的堆顶往下调整找到次大的值重复步骤2 其实相当于第一个元素默认是堆后面的进行遍历调整 //排序,升序
void HeapSort(int* parr, int n)
{//1.建立大堆for (int i 1;i n; i){justUp(parr, i);}//2.堆顶元素与堆尾元素互换然后将堆size-1指只需要遍历到的位置int end n - 1;while (end0){//堆顶和堆尾 元素呼唤Swap(parr[0], parr[end]);//往下调整justDown(parr,end,0);end--;}
} 也有其他思路 我们从下面子树往上遍历而内部调整时往下调整 n-1是最后结点下标值结点-1/2 可以得到该结点的父结点从父结点往下调整 for (int i (n-1-1)/2; i 0; --i){AdjustDown(parr, n, i);}Top-k问题 在排序的基础上如果这个数很大呢比如一百万个数要找到前k个较大值 此刻建堆排序显然不合适 1.读取前K个值建立其小堆 2.依次读取后面的值与堆顶比较如果比堆顶大替换堆顶进堆再往下调整 创建数据
//tok-k 问题
//创建一千万的数据
void CreateNode()
{// 造数据int n 10000000;srand(time(0));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() i) % 10000000; //i是 因为随机数产生只有三万个加上i可以大大减少重复值fprintf(fin, %d\n, x);}fclose(fin);
}
堆top-k 开辟K个数的空间动态数组 建立K个数的小堆 读取文件中值遍历与堆顶比较 void HeapTok(const char* file,int k)
{FILE* fout fopen(file, r);if (fout NULL){perror(fopen error);return;}//开辟K个数的空间int* minheap (int*)malloc(sizeof(int) * k);if (minheap NULL){perror(malloc error);return;}//建立K个数的小堆for (int i 0; i k; i){//从文件流中 读取数据存到 开辟的空间中fscanf(fout,%d, minheap[i]);//往上调整AdjustUp(minheap, i);}//遍历文件数据 int x 0;while (fscanf(fout, %d, x) ! EOF) {if (x minheap[0]){minheap[0] x;//往下调AdjustDown(minheap, k, 0);}}//打印tokfor (int i 0; i k; i){printf(%d , minheap[i]);}free(minheap);fclose(fout);
}
