【数据结构】建堆、堆的向下调整及其复杂度、堆的向上调整及其复杂度、Top |
您所在的位置：网站首页 › 向下调整和向上调整的区别 › 【数据结构】建堆、堆的向下调整及其复杂度、堆的向上调整及其复杂度、Top |
【数据结构】建堆、堆的向下调整及其复杂度、堆的向上调整及其复杂度、Top
|
目录
一.完全二叉树的顺序结构二.堆的概念及结构三.堆的实现1.堆向下调整2.向下调整建堆3.向下调整建堆时间复杂度4.堆的插入（向上调整）5.向上调整建堆6.向上调整建堆时间复杂度7.堆的删除8.向下调整和向上调整的使用类型9.堆的代码实现
四.Top-K问题五.堆排序六.总结
一.完全二叉树的顺序结构
堆的逻辑结构采用完全二叉树，而堆就是在一定条件下将完全二叉树使用数组存储，我们可以利用完全二叉树更好的学习堆。 普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构（数组）存储。 如上图该完全二叉树（按从上到下，从左到右顺序存储）的数组结构就叫做堆（上图的数组满足条件所以可以叫做堆，条件下面会讲） 需要注意，这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。 二.堆的概念及结构那是不是只要是一个完全二叉树，把它按顺序放在数组里就是一个堆呢？当然不是 堆的种类分为两种： 一个堆中某个节点的值总是不大于其父节点的值叫：大堆一个堆中某个节点的值总是不小于其父节点的值叫：小堆
只有满足这两点的数组才可以被称之为堆 三.堆的实现现在给出一个数组，逻辑上看做是一颗完全二叉树。我们已经知道堆分为大堆和小堆两种，那我们要如何才能将它变成一个完整的堆呢？ int arr[8] = { 7,4,2,9,3,4 };
这里就需要先来学一种方法完成堆的构建：堆向下调整 1.堆向下调整按照完全二叉树的逻辑结构，从最后一个节点的父节点开始，以该节点下标为起始，与自己的两个孩子节点（可能为一个孩子节点）比较大小并根据情况交换位置（大堆比较更大的孩子节点，小堆比较更小的孩子节点），一直调整到根节点，最终得到大堆/小堆 向下调整算法的前提：根节点的左右子树必须都为堆，才能调整，否则在本就无序的情况下去，去使用根节点的值去比对查找，是无法找到适合的元素的，所以向下调整只能从最后一个节点的父节点开始（也可以说是倒数的第一个非叶子节点）对比，从后向前依次建堆，才能保证每个结点在进行向下调整时左右子树都为堆。我们在这些做一个大堆并画出它的流程图：
我们之前以及提过了，这个堆的存储形式是一个数组，而最后一个节点就是数组下标最大的元素，那我们要如何求出它的父节点？ 这个是有固定的公式，根据这个公式： 当我们知道孩子节点的下标就能求出其父节点的下标，知道父亲节点的下标，就能求出孩子节点的下标， 下标如下图：
知道父亲节点下标，求孩子节点下标 father = 0 ： 左孩子 = father * 2 + 1 = 1； 右孩子 = father * 2 + 2 = 2； father = 3 ： 左孩子 = father * 2 + 1 = 7； 右孩子 = father * 2 + 2 = 8； 知道父亲节点，求孩子节点的公式如下： 左孩子 = father * 2 + 1； 右孩子 = father * 2 + 2； 知道孩子节点下标，求父亲节点下标 知道左孩子下标 由上面的公式推导：father = (左孩子-1)/2; 知道右孩子下标 由上面的公式推导：father = (右孩子-2)/2; 其中，左孩子一定是奇数，右孩子是偶数，而在C语言中，一个偶数减1后除以2和一个偶数减2后除以2是相同的，因为下标为整数，偶数减1后除以2所得必须为整数，除不尽的部分直接舍弃。 因此，我们不需要知道该孩子节点是左孩子还是右孩子。 知道孩子节点下标，求父亲节点下标公式如下： father = (孩子-1)/2； 2.向下调整建堆我们已经知道了一个堆是如何创建的，现在有如下数组，我们使用代码来实现堆的创建。 int arr[8] = { 7,4,2,9,3,4,5,6 };代码如下： void swap(int* a1, int* a2) { int tmp = *a1; *a1 = *a2; *a2 = tmp; } void AdjustDown(int* arr, int n, int father)//向下调整 { int child = father * 2 + 1;//左孩子节点下标 while (child swap(&arr[father], &arr[child]);//两节点进行交换 father = child;//孩子结点的下标赋给父亲结点 child = father * 2 + 1;//孩子节点获得新的左孩子下标 } else break; } } int CreatHeap(int* arr, int n)//arr为要建堆的数组 { for (int i = (n - 1 - 1) / 2; i >= 0; i--)//循环的初始值为倒数第一个非叶子节点的下标 { AdjustDown(arr, n, i);//向下调整 } } 3.向下调整建堆时间复杂度时间复杂度是求该函数在最坏的情况下基本操作次数，而我们现在算的是建堆这一功能的时间复杂度，因为堆是完全二叉树，而满二叉树（除叶子节点外，每个节点都有两个孩子节点）也是完全二叉树，此处我们就能使用满二叉树来判断堆的时间复杂度。
如下图所示，我们在原有完全二叉树的基础上，向其中尾插一个10，之后就需要进行向上调整，做法如下图： 该堆为小堆，先找到新插入节点的父节点，进行对比，父节点大，进行替换，新插入的节点取代父节点，并向新的父节点进行对比操作，直到到达根节点。若是父节点小于新插入的节点，停止操作，表面堆的插入以完成。 注意：这里最好不要用向下调整，堆的插入操作是在一个堆已经成型的情况下进行，如果用向下调整，新插入的节点的父节点后的所有节点都要重新遍历一遍，时间复杂度一定要比只是移动新节点的向上调整大。 知道孩子节点，如何求父节点的公式之前已经讲了，这里我们就能直接得出代码（这里做的是小堆的插入）： 向上调整代码如下： void AdjustUp(int* arr, int child) { int father = (child - 1) / 2;//获得父亲节点的下标 while (child) { if (arr[father] > arr[child])//孩子结点数据小于父亲结点数据，两数交换 { swap(&arr[father], &arr[child]); child = father; father = (child - 1) / 2; } else break; } } 堆中的结点个数为：n = h^2 - 1; 堆中的层数为：h = log(n+1); 堆插入的时间复杂度为堆的层数，时间复杂度为：O(logN)如果使用向下调整完成堆插入，相当于在经历一遍建堆，因为堆已经建好，所以比较的次数相比初次建堆要小，但终归没有直接向上排序来的快。 5.向上调整建堆我们在堆的插入中已经学了堆的向上调整的思想，我们也可以利用向上调整来建堆，但是这个时间复杂度要大于向下调整，实际操作中不会用到这个方法建堆，这里简单介绍一下。
 代码如下：
void AdjustUp(int* arr, int child)
{
int father = (child - 1) / 2;//获得父亲节点的下标
while (child)
{
if (arr[father] > arr[child])//孩子结点数据小于父亲结点数据，两数交换
{
swap(&arr[father], &arr[child]);
child = father;
father = (child - 1) / 2;
}
else
break;
}
}
void CreatHeap(int* a,int n)
{
for (int i = 0; i
HPDataType* _a;
int _size;
int _capacity;
}Heap;
堆的其他功能实现难度不大，这里就只整体展示代码，不一个个讲解了。 注意：下面代码中一些类型用自定义结构体类型交换，与上面实现的代码相同 堆的所有功能代码如下; //打印堆 void PrintHeap(Heap* hp) { assert(hp); for (int i = 0; i size; i++) { printf("%d ", hp->a[i]); } printf("\n"); } void HeapInit(Heap* hp) { hp->a = NULL; hp->capacity = 0; hp->size = 0; } // 堆的销毁 void HeapDestory(Heap* hp) { assert(hp); free(hp->a); hp->a = NULL; hp->capacity = 0; hp->size = 0; } 堆的构建——偷懒的写法——使用向上调整实现堆的构建 //void HeapCreat(Heap* hp, HPDataType* a, int n) //{ // hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n); // if (!hp->a) // { // perror("malloc fail!"); // exit(-1); // } // hp->capacity = n; // // for (int i = 0; i < n; i++) // { // HeapPush(hp, a[i]); // } //} //堆的构建——建堆算法 void HeapCreat(Heap* hp, HPDataType* a, int n) { hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n); if (!hp->a) { perror("malloc fail!"); exit(-1); } memcpy(hp->a, a, sizeof(HPDataType) * n); hp->capacity = hp->size = n; //建堆算法——函数接收父亲结点算法 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(hp->a, n, i); } } //两数交换 void swap(HPDataType* a1, HPDataType* a2) { HPDataType tmp = *a1; *a1 = *a2; *a2 = tmp; } //向上调整 void AdjustUp(HPDataType* arr, int child) { int father = (child - 1) / 2;//父亲结点位置 while (child) { if (arr[child] > arr[father])//孩子结点数据大于父亲结点数据，两数交换 { swap(&arr[child], &arr[father]); child = father; father = (child - 1) / 2; } else break; } } // 堆的插入 void HeapPush(Heap* hp, HPDataType x) { assert(hp); if (hp->capacity == hp->size) { int newSize = hp->capacity * 2; HPDataType* newArr = (HPDataType*)realloc(hp->a, newSize); if (!newArr) { perror("realloc fail!"); exit(-1); } hp->capacity = newSize; hp->a = newArr; } hp->a[hp->size++] = x; AdjustUp(hp->a, 0); } //向下调整 void AdjustDown(HPDataType* arr,int n,int parent) { int child = parent * 2 + 1; while (child swap(&arr[parent], &arr[child]); parent = child; child = parent * 2 + 1; } else break; } } // 堆的删除 void HeapPop(Heap* hp) { assert(hp); assert(hp->size); hp->a[0] = hp->a[--hp->size]; AdjustDown(hp->a, hp->size, 0); } //取堆顶的数据 HPDataType HeapTop(Heap* hp) { assert(hp); assert(hp->size > 0); return hp->a[0]; } //堆的数据的个数 int HeapSize(Heap* hp) { assert(hp); return hp->size; } //判空 int HeapEmpty(Heap* hp) { assert(hp); return hp->size == 0; } 四.Top-K问题问题：在一个很大的数据中，取出它最大或最小的前k个值。 比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于这个问题，想到最简单的方法就是排序，但是数据量非常大，当数据不可能一下子全部加载到内存中时，排序就不太可取了。 最佳的方法就是用堆来解决，基本思路如下： 1. 用数据集合中前k个元素来建堆 取前k个最大的元素，建小堆取前k个最小的元素，建大堆2.用剩余的N-k个元素依次与堆顶元素来比较，不满足则替换堆顶元素，在进行向下调整。 将剩余N-k个元素依次与堆顶元素比较完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 如下图，为取前6个最大的元素的一次对比图：
具体代码如下： void TopK(int* arr,int n,int k) { int* tmpArr = (int*)malloc(sizeof(int) * k); //方法1 //memcop(tmpArr, arr, sizeof(int) * k);//使用内存函数拷贝数组前k个数 //方法2 for (int i = 0; i AdjustDown(tmpArr, k, i);//向下调整建堆 } for (int i = k; i swap(&arr[i], &tmpArr[0]); AdjustDown(tmpArr, k, 0);//将此时栈顶的元素进行向下调整 } } for (int i = 0; i int child = father * 2 + 1;//左孩子节点下标 while (child swap(&arr[father], &arr[child]);//两节点进行交换 father = child;//孩子结点的下标赋给父亲结点 child = father * 2 + 1;//孩子节点获得新的左孩子下标 } else break; } } int* HeapSort(int* arr,int n) { for (int i = (n-1-1)/2; i >= 0; i--)//先建堆 { AdjustDown(arr, n, i); } for (int i = 0; i |
我们得出堆的性质：
因为需要按照最坏的情况考虑，我们就将堆中除最后一层外的其他节点都需要向下移动到最底层。 
所以：建堆的时间复杂度为O(N)
【本文地址】