二叉树——堆的排序 TOP-K算法
二叉树——堆
堆的排序
这里排序无非就是升序和降序，那么，之前用的冒泡排序时间复杂度是很高的，所以这次来了解一个更加高效率的。
建堆
建堆的过程有两种，一是向上调整法，另一种是向下调整法，但是更快的是向下调整法，因为堆是类似于一个三角形，越往下，元素就越多，向上调整，堆顶的结点一定不用在向上调整了，因为堆顶上面没有父节点了，而向下调整法是叶子结点不用在向下调整了，因为叶子结点是最后的结点，下面没有子结点。 那么，肯定是向下调整法的时间复杂度比较低。 代码实现
void swap(int* p1, int* p2)//交换数据
{
int p = *p1;
*p1 = *p2;
*p2 = p;
}
void upward(int* a,int size,int parent)//向下调整
{
int minchild = 2 * parent + 1;//表示最小的孩子，第一次先假设左孩子最小
while (minchild < size)//防止数组越界
{
if (minchild + 1 < size && a[minchild + 1] > a[minchild])//防止右孩子出界
{
minchild++;//如果右孩子比左孩子小就让右孩子等于最小
}
if (a[minchild] > a[parent])//判断是否需要向下调整
{
swap(&a[minchild], &a[parent]);
parent = minchild;
minchild = 2 * parent + 1;
}
else
{
break;
}
}
}
void sort()
{
int arr[] = { 10,6,3,4,9,10,81 };//随机数组
int n = sizeof(arr) / sizeof(arr[0]);//数组有效数的长度
for (int i = (n - 1 - 1) / 2; i >= 0; --i)//这里(n-1-1)/2是因为找下标需要-1，然后剩下公式的是找到最后一个叶子节点的父母
{//遍历除叶子结点外所有结点
upward(arr, n, i);
}
}利用堆删除思想来进行排序
建堆的时间复杂度是O(N)，之前说过向下查找法和向上查找法，时间复杂度是O(logN). 大堆是父结点比子结点大，小堆则相反，我们用堆排序的核心思路是类似于删除的逻辑，因为在堆顶不是最大的就是最小的，我们把堆顶的元素和尾部交换然后再进行排序就可以了。 那么，降序要用小堆，升序用大堆。 例：降序，图像理解
然后让5之前的数进行向下调整，从而不打乱小堆的结构。
再让堆顶的10与30交换
最后以此类推。 例：升序，代码实现
void swap(int* p1, int* p2)//交换数据
{
int p = *p1;
*p1 = *p2;
*p2 = p;
}
void upward(int* a,int size,int parent)//向下调整
{
int maxchild = 2 * parent + 1;//表示最大的孩子，第一次先假设左孩子最小
while (maxchild < size)//防止数组越界
{
if (maxchild + 1 < size && a[maxchild + 1] > a[maxchild])//防止右孩子出界
{
maxchild++;//如果右孩子比左孩子大就让右孩子等于最大
}
if (a[maxchild] > a[parent])//判断是否需要向下调整
{
swap(&a[maxchild], &a[parent]);
parent = maxchild;
maxchild = 2 * parent + 1;
}
else
{
break;
}
}
}
void sort()
{
int arr[] = { 10,6,3,4,9,10,81 };//随机数组
int n = sizeof(arr) / sizeof(arr[0]);//数组有效数的长度
for (int i = (n - 1 - 1) / 2; i >= 0; --i)//这里(n-1-1)/2是因为找下标需要-1，然后剩下公式的是找到最后一个叶子节点的父母
{//遍历除叶子结点外所有结点
upward(arr, n, i);//建大堆
}
int i = 1;
while (i < n)//因为最终要排序n-1次
{
swap(&arr[0],&arr[n-i]);//交换首尾
upward(arr, n - i, 0);//向下调整，保持小堆
++i;
}
int j = 0;
for (j = 0; j < n; ++j)
{
printf("%d ", arr[j]);
}
}
TOP-K算法
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。 对于Top-K问题，能想到的最简单直接的方式就是排序O(N*logN)，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
用数据集合中前K个元素来建堆
假如数组里面的数有N个（非常大），然后找K（非常小）前面的元素，那么就用建立大堆然后再进行删除的操作，也就是首尾交换。 例如：如果是寻找数组中前K个最大元素，那么时间复杂度就是建堆和找数的时间，找数只要找K次就可以了。O(N+logN*K) 但是如果N很大，K很小时间复杂度也是很高，所以这里创建小堆。 小堆方法 用数组中前K个数建立一个小堆，小堆的容量也就是我们需要的数量，这时就需要交换小堆里面的数了，因为堆顶的数是最小的，所以我们遍历K后面的数，也就是N-K个数，如果比堆顶的大就和堆顶交换，之后再进行向下调整。
时间复杂度为O(K+logK*(N-K)) 因为K很小的原因，所以就约等于O(N) 结论如下：
- 前k个最大的元素，则建小堆
- 前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 代码实现
void swap(int* p1, int* p2)//交换数据
{
int p = *p1;
*p1 = *p2;
*p2 = p;
}
void upward(int* a,int size,int parent)//向下调整
{
int minchild = 2 * parent + 1;//表示最小的孩子，第一次先假设左孩子最小
while (minchild < size)//防止数组越界
{
if (minchild + 1 < size && a[minchild + 1] < a[minchild])//防止右孩子出界
{
minchild++;//如果右孩子比左孩子小就让右孩子等于最小
}
if (a[minchild] < a[parent])//判断是否需要向下调整
{
swap(&a[minchild], &a[parent]);
parent = minchild;
minchild = 2 * parent + 1;
}
else
{
break;
}
}
}
void random(char* p, int n)//向文件中写入随机数
{
FILE* p1 = fopen(p, "w");//写文件，让p1指向文件位置
if (p1 == NULL)
{
perror("fopen fail");
exit(-1);
}
srand(time(0));//随机数的起点
for (int i = 0; i < n; ++i)//向文件中写入随机数
{
fprintf(p1, "%d ", rand()%1000);//这里不让随机数超过1000方便观看
}
fclose(p1);
}
void TestTopk(char* p, int k)
{
FILE* p1 = fopen(p, "r");//打开文件，让p1指向文件位置
if (p1 == NULL)
{
perror("fopen fail");
exit(-1);
}
int* p2 = (int*)malloc(sizeof(int) * k);//开辟堆的空间
if (p2 == NULL)
{
perror("malloc fail");
exit(-1);
}
for (int i = 0; i < k; i++)//读取k之前的数
{
fscanf(p1, "%d", &p2[i]);//把文件前k歌数读取到新建堆中
}
for (int j = (k - 1 - 1) / 2; j >= 0; --j)
{
upward(p2, k, j);//建小堆
}
int a = 0;
while (fscanf(p1, "%d", &a) != EOF)//读取K之后的数
{
if (a > p2[0])
{
p2[0] = a;
upward(p2, k, 0);//向下调整
}
}
for (int i = 0; i < k; ++i)
{
printf("%d ", p2[i]);//打印k之前的数据
}
fclose(p1);
free(p2);
}
int main()
{
const char* p = "TOP-K.txt";//自己创建一个文件
int k = 10;
int n = 100;
random(p, n);
TestTopk(p, k);
return 0;
}腾讯云开发者
