怎么介绍自己做的企业网站页面,网站建设 补充协议,wordpress建站小百科,wordpress 优秀插件文章目录 一、堆的概念及结构二、堆的实现1.向上调整算法2.向下调整算法3.堆的创建4.堆的插入5.堆的删除6.堆的其他操作 三、堆的应用1.堆排序2.Top-K问题 一、堆的概念及结构 堆(Heap)是一种特殊的非线性结构。堆中的元素是按完全二叉树的顺序存储方式存储在数组 中。满足任意… 文章目录 一、堆的概念及结构二、堆的实现1.向上调整算法2.向下调整算法3.堆的创建4.堆的插入5.堆的删除6.堆的其他操作 三、堆的应用1.堆排序2.Top-K问题 一、堆的概念及结构 堆(Heap)是一种特殊的非线性结构。堆中的元素是按完全二叉树的顺序存储方式存储在数组 中。满足任意结点的值都大于等于左右子结点的值叫做大堆或者大根堆反之则是小堆或者小根堆。 不熟悉二叉树的小伙伴可以先跳转→二叉树详解←学习。
堆分为小根堆和大根堆。
小根堆所有父结点都小于等于左右孩子结点。 大根堆所有父结点都大于等于左右孩子结点。 堆的性质 1.堆是一棵完全二叉树。 2.堆中某个节点的值总是不大于或不小于其父节点的值。 3.如果一个堆为大小根堆则它的左右子树也都是大小根堆。 4.小堆的存储结构不是升序大堆的存储结构也不是降序。 5.堆中任意结点下标为 i则它的左孩子结点下标为2i1右孩子结点下标为2i2父结点下标为(i-1)/2。 二、堆的实现
堆的两个重要算法向上调整和向下调整。
1.向上调整算法
向上调整一般在堆中插入元素时使用。 具体实现(小根堆示例) 1.给定一个数组和一个结点下标该结点与其父结点的值进行比较。 2.如果该结点的值 ≥ 其父结点的值已经是小堆了则不再继续调整 3.如果该结点的值 其父结点的值需要将二者交换然后将父结点当做孩子结点继续向上对比和交换直到调整到堆顶。 如果是小根堆只需要改变判断符号改为即可。
//小根堆 向上调整
void AdjustUp(DataType* a, int child)
{int parent (child - 1) / 2;//父结点下标while (a[child] a[parent])//建大堆{Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}
}
//交换函数
void Swap(DataType* p1, DataType* p2)
{DataType tmp *p1;*p1 *p2;*p2 tmp;
}向上调整算法的比较次数最多不超过二叉树的高度所以时间复杂度为O(logN) 2.向下调整算法
堆的向下调整算法比较常用堆排序和堆的创建都会用到向下调整算法。
向下调整算法有一个前提左右子树必须是一个堆才能调整。 具体实现(小根堆示例) 1.从该结点开始与其左右孩子结点中比较大较小的结点进行比较。 2.如果该结点的值 ≤ 其较小较大孩子结点的值已经是小堆了则不再继续调整 3.如果该结点的值 其较小较大孩子结点的值需要将二者交换然后将较小的孩子结点当做父结点继续向下对比和交换直到调整到叶子结点。 //向下调整
void AdjustDown(DataType* a, int parent, int n)
{int child 2 * parent 1;while (child n){//选出较小的孩子if (child 1 n a[child 1] a[child])//右孩子不能越界访问注意判断顺序不能反{child;}if (a[parent] a[child]){Swap(a[parent], a[child]);parent child;child 2 * parent 1;}else{break;}}
}同样向下调整算法的比较次数最多也不会超过二叉树的高度所以时间复杂度为O(logN) 3.堆的创建
给定一个数组怎么创建成一个堆呢 根结点的左右子树都不是堆该怎么调整
向上调整建堆
从根结点开始调整 从根结点的左孩子结点开始因为根结点本身可以看做一个堆每个结点都向上调整此时该结点前面的所有结点都已经构成了一个堆直到调整到最后一个结点就可以调整成堆。 // 向上调整建堆 效率O(N*logN)
for (int i 1; i n; i)
{AdjustUp(a, i);
}向上调整建堆的时间复杂度是多少 每个结点最多需要向上调整的次数与层数有关若层数为k则最多最多向上调整logk次。而随着层数越大每层的结点数也越多。假设二叉树的高度为h则向上调整为堆最多需要调整的次数为0×201×212×223×23…(h-1)×2h-1 (h-2)×2h错位相减高中知识具体过程略又因为树的高度hlog(n1)所以时间复杂度的量级为O(N*logN)。 向下调整建堆
从最后一个非叶子结点开始倒着调整 因为向下调整建堆需要满足左右子树都是堆的前提所以我们可以从最后一个结点开始依次向下调整因为最后一个结点本身可以看做是一个堆。但是因为叶子结点向下调整并不会发生变化所以我们可以优化代码从最后一个叶子结点的父结点也就是最后一个非叶子结点开始调整。 //向下调整建堆 效率O(N)
for (int i (n - 1 - 1) / 2; i 0; i--)
{AdjustDown(a, i, n);
}向下调整建堆的时间复杂度是多少 因为向下调整建堆是从最后一个非叶子结点开始倒着调整的随着层数的减小每层的结点数也越少但是结点向下调整的次数在增加具体推导过程这里不过多介绍最后的时间复杂度的量级是O(N)。 综上所述向上调整建堆的时间复杂度为O(N*logN)向下调整建堆的时间复杂度为O(N)所以使用向下调整建堆的效率更高效。实际应用中一般都使用向下调整算法建堆。
堆的定义、初始化、销毁 堆是以数组的方式存储的所以堆的定义、初始化、销毁和顺序表一样。
#define INIT_SZ 10//初始空间大小
#define INC_SZ 4 //每次扩容的数量
typedef int HDataType;
typedef struct Heap
{HDataType* a;int size;int capacity;
}Heap;//初始化
void HeapInit(Heap* php)
{assert(php);php-a (HDataType*)malloc(sizeof(HDataType) * INIT_SZ);if (NULL php-a){perror(malloc);return;}php-size 0;php-capacity INIT_SZ;
}//销毁
void HeapDestroy(Heap* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}4.堆的插入
堆的插入需要用到向上调整算法。 实现步骤 1.在堆的末尾插入一个元素 2.该元素向上调整直到满足堆的性质。 //入堆
void HeapPush(Heap* php, HDataType x)
{assert(php);//扩容if (php-size php-capacity){HDataType* tmp (HDataType*)realloc(php-a, sizeof(HDataType) * (INC_SZ php-capacity));if (NULL tmp){perror(malloc);return;}php-a tmp;php-capacity INC_SZ;}php-a[php-size] x;//尾插AdjustUp(php-a, php-size - 1);//向上调整
}5.堆的删除
删除的是堆顶的元素删除之后仍然保证是堆 堆的删除需要用到向下调整算法。 实现步骤 1.将堆顶元素与最后一个元素交换 2.堆长度-1即删除最后一个位置 3.将交换后的堆顶元素向下调整。 void HeapPop(Heap* php)
{assert(php);assert(!HeapEmpty(php));//将尾数据和堆顶数据交换交换后的堆顶元素再向下调整Swap(php-a[php-size - 1], php-a[0]);php-size--;//堆的有效长度-1AdjustDown(php-a, 0, php-size);
}6.堆的其他操作
//返回堆顶元素
HDataType HeapTop(Heap* php)
{assert(php);return php-a[0];
}
//判堆空
bool HeapEmpty(Heap* php)
{assert(php);return php-size 0;
}
//堆的元素个数
int HeapSize(Heap* php)
{assert(php);return php-size;
}三、堆的应用
1.堆排序
从前面的学习我们知道堆结构的层序遍历也就是从上到下每一层的从左到右并非是有序的也就是说堆存储在数组中的数据并不是有序的。比如下面这个大根堆在数组中就是10,5,9,4,3,1,7 我们如何利用堆的特性将这些数据排序呢 我们知道大根堆的堆顶一定是最大的小根堆的堆顶一定是最小的所以利用这一个特点我们可以取出堆顶元素然后将剩下的元素重新调整成堆再取堆顶元素再调整剩下的元素依次类推直到最后一个元素就可以实现堆排序了。
但是如果我们将堆顶元素按兵不动将剩下的元素原地调整成堆但剩下的元素会被完全打乱完全不符合堆的性质需要重新建堆最后虽然也可以排序但是效率却很低。这样的话跟普通排序没什么区别每次找最大值最小值就好了并没有用到堆的优势。 堆排序的实现步骤 1.先将数组建堆 2.将堆顶元素与堆末尾元素交换 3.堆有效长度-1 4.再将堆顶元素向下调整直到调整到成堆 这不就是先建一个堆再进行堆的删除操作吗没毛病原理是一样的。 比如一个大根堆我们取出堆顶元素最大数与最后一个数交换交换后的最大数不看作在堆里面那么堆顶元素的左右子树仍满足堆的性质堆的结构并没有被破坏然后堆顶元素向下调整成堆即可选出第二大的数以此类推到最后一个元素就可以成功实现堆排序了。 堆排序就是每次将堆顶元素从数组的末尾往前放所以排升序建大堆排降序建小堆
//堆排序
void HeapSort(int* a, int n)
{//建堆排升序建大堆排降序建小堆//倒着调整从最后一个非叶子结点开始向下调整建堆 效率O(N)for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, i, n);}//O(N*logN)int end n - 1;//堆的有效长度while (end 0){Swap(a[0], a[end]);AdjustDown(a, 0, end);end--;}
}堆排序的时间复杂度是O(N*logN) 2.Top-K问题
Top-K问题求集合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如游戏中排行榜前50名全校前10名等。
对于Top-K问题自然第一个想到的就是排序没毛病。但是数据量很大的情况下排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。
第二种方法就是用堆来解决。 实现方法 用数据集合中前K个元素来建堆。 前k个最大的元素则建小堆 前k个最小的元素则建大堆用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素。比较完后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 如果选前k个最大值需要建小堆。 原理分析小堆的堆顶元素是这k个数据中最小的元素如果剩下N-K个元素中有大于堆中最小值的说明这个数可以进入前k名如果剩下N-K个元素中有小于堆中最小值的则无法进入前k名。但是如果建大堆的话堆顶元素就无法作为标准了。
void TopK(int* a, int n, int k)
{//用a中前k个元素建堆for (int i (k - 2) / 2; i 0; i--)AdjustDown(a, i, k);for (int i k; i n; i){if (a[i] a[0]){Swap(a[i], a[0]);//不满足则交换AdjustDown(a, 0, k);//向下调整}}for (int i 0; i k; i)printf(%d , a[i]);
}上述代码只是选出前k个最大值或最小值并没有将这k个数排序如果要实现排序功能自行添加即可。
堆的完整代码放在giteehttps://gitee.com/ncu-ball/study/tree/master/24_4_19
