北京市网站建设,沈阳自助建站软件,做网站哪,官网域名改版方案目录 堆的概念及结构 编辑 堆的实现 实现堆的接口 堆的初始化 堆的打印 堆的销毁 获取最顶的根数据 交换 堆的插入#xff08;插入最后#xff09; 向上调整#xff08;这次用的是小堆#xff09; 堆的删除#xff08;删除根#xff09; 向下调整#xff08;这次用的… 目录 堆的概念及结构 编辑 堆的实现 实现堆的接口 堆的初始化 堆的打印 堆的销毁 获取最顶的根数据 交换 堆的插入插入最后 向上调整这次用的是小堆 堆的删除删除根 向下调整这次用的小堆 堆排序 TOP-K问题 堆的概念及结构 如果有一个关键码的集合 K { … }把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足 且 ( 且 ) i 0 1 2…则称为小堆 ( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树。 小根堆父亲节点大于等于孩子节点 大根堆父亲节点小于等于孩子节点 堆的实现
实现堆的接口
#define CRT_SECURE_NO_WARNING 1
#pragma once
#includestdio.h
#includestdlib.h
#includestring.h
#includeassert.h
#includestdbool.h//二叉树-堆
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void AdjustUp(HPDataType* a, int child);void AdjustDown(HPDataType* a, int n, int parent);//交换
void Swap(HPDataType* p1, HPDataType* p2);
//打印
void HeapPrint(HP* php);
//初始化
void HeapInit(HP* php);
//
void HeapInitArray(HP* php, int* a, int n);
//销毁
void HeapDestroy(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//删除
void HeapPop(HP* php);
//返回最顶数据
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);
堆的初始化
//初始化
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}
堆的打印
void HeapPrint(HP* php)
{assert(php);//最后一个孩子下标为size-1for (size_t i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}堆的销毁
//销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}
获取最顶的根数据
//获取根数据
HPDataType HeapTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
堆的插入插入最后
先考虑扩容将数据插到最后再用向上调整法。
//插入数据
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php-size php-capacity)//有效元素个数和容量是否相等{//相等的情况分两种1.容量为0先扩4个sizeof 2.容量占用满了,扩2个int newCapacity php-capacity 0 ? 4 : php-capacity * 2;//返回扩容后的内存新地址 //扩容后的新大小HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}//扩容后的新地址php-a tmp;//新容量php-capacity newCapacity;}// php-size下标位置 先将x放最后后面再调整php-a[php-size] x;// 有效数据php-size;// 向上调整 //size-1为新插入数据的下标AdjustUp(php-a, php-size - 1);}
向上调整这次用的是小堆
向上调整的前提左右子树是堆 时间复杂度O(logN)
//向上调整 //新插入的数据下标
void AdjustUp(HPDataType* a, int child)
{ //定义其父节点的下标int parent (child - 1) / 2;//循环while (child 0){//如果子小于父就交换 小堆if (a[child] a[parent]){//数值交换Swap(a[child], a[parent]);//下标child parent;parent (parent - 1) / 2;}else{break;}}
}
堆的删除删除根
先判空看下是否还有元素可以删除。根数据先和最后一个孩子交换位置孩子再向下调整。
//删除
void HeapPop(HP* php)
{assert(php);//确保有元素可删assert(php-size 0);//最后一个孩子和要删除的根交换Swap(php-a[0], php-a[php-size - 1]);//有效元素size减减相当于删除了交换后的原来的根--php-size;//删除后向下调整AdjustDown(php-a, php-size, 0);}
向下调整这次用的小堆
向下调整的前提左右子树是堆
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child parent * 2 1;//n下标位置已经没有数了while (child n){//选小的孩子往上浮小堆if (child 1 n a[child 1] a[child]){child;}//若小的孩子都小于父则交换if (a[child] a[parent]){Swap(a[child], a[parent]);//交换后下来的数重新变成parent继续向下调整parent child;child parent * 2 1;}}
}
堆排序 1. 建堆 升序建大堆 降序建小堆 2. 利用堆删除思想来进行排序 建堆向上调整法建堆的时间复杂度O(N*logN) 向下调整法建堆的时间复杂度O(N) 可以用堆删除思想向下调整法将栈顶和最后一个元素交换依次将最大的次大的......往后放就达到了升序排列。 void HeapSort(int* a, int n)
{//建堆 这里可以选建大堆还是小堆// 向下调整建堆// O(N)for (int i (n-1-1)/2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}
TOP-K问题 TOP-K 问题即求数据结合中前 K 个最大的元素或者最小的元素一般情况下数据量都比较大 。 比如专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。 对于 Top-K 问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了 ( 可能 数据都不能一下子全部加载到内存中 ) 。最佳的方式就是用堆来解决基本思路如下 1. 用数据集合中前 K 个元素来建堆 前 k 个最大的元素则建小堆 前 k 个最小的元素则建大堆 2. 用剩余的 N-K 个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K 个元素依次与堆顶元素比完之后堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素 先创建一个包含有10000000个数的data.txt文本文件。 void CreateNDate()
{// 造数据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;fprintf(fin, %d\n, x);}fclose(fin);
}
前k个建小堆堆顶元素为k中最小剩余n-k个依次和堆顶元素比较比k大就插入堆中插入堆插入向下调整法完成后打印前k个元素。
void PrintTopK(const char* filename, int k)
{// 1. 建堆--用a中前k个元素建堆FILE* fout fopen(filename, r);if (fout NULL){perror(fopen fail);return;}//给堆开辟空间int* minheap (int*)malloc(sizeof(int) * k);if (minheap NULL){perror(malloc fail);return;}for (int i 0; i k; i){fscanf(fout, %d, minheap[i]);}// 前k个数建小堆for (int i (k - 2) / 2; i 0; --i){AdjustDown(minheap, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换不满则则替换int x 0;while (fscanf(fout, %d, x) ! EOF){if (x minheap[0]){// 替换你进堆minheap[0] x;AdjustDown(minheap, k, 0);}}for (int i 0; i k; i){printf(%d , minheap[i]);}printf(\n);free(minheap);fclose(fout);
}假设k等于5成功打印出前5个最大的数据
