C语言用堆思想解决TopK问题

之前介绍了堆的一些操作，对堆排序的操作是在提前创建了堆的数据结构的基础上直接调用以前的数据结构，但是今天我们要做的是，假如现在你去面试或者遇到问题的时候没有堆这个数据结构可以直接调用的时候怎么办呢？难道要现场创建一个吗？也不是说不可以，但是毕竟你的时间是有限的，而且其实可以通过直接对数组的操作来进行堆的操作。

  其实TopK问题就是复杂之后的堆排序问题，所以今天我主要给大家介绍一个TopK问题，其实TopK问题简单来说就是在海量的数据中找到最大的K个数值。就那我们正常的排序来看例如：冒泡排序，在解决海量数据的时候我们就要考虑你程序的复杂度。包括现在很多程序也是，你实现你的思想并不难，难的是你的算法，你有一个好的算法就等于让你的程序有了更高的智商来解决这个问题。就能又快有准解决你所想要解决的问题。继续说我们之前所熟悉的冒泡排序，这里大家学了时间复杂度之后都知道，冒泡排序是一个时间复杂度为O（n）的处理程序，当你有1500个数据的时候你就需要2250000次计算，并且当随着你的数据的不断增加，这个数量是急剧增长的。所以在我们处理更多的数据的时候就需要好的算法。

 这里就是用到了我们的堆，首先还是之前的问题，TopK是找到最大的K个数据，既然是这样，那是不是就意味着，和我们之前对堆的操作一样，现在将你的海量数据进行建造大堆等堆创建好了之后，选出来最大的一个，也就是堆顶的数据，然后让最后一个补上来，继续开始一次向下调整。这样实现起来是没有任何问题的，但是在我们看起来他并没有那么的简单，那么的方便。这里有没有更好的办法呢？我其实你想假如你现在的前K个元素正好就是最大的元素，那当你创建好整个堆之后，你还是需要不断的去掉顶，然后不断的去向下调整。这里有没有有点更好的办法呢？

  其实说到这里我想大家也有一定的思路了，那就是我要TOP的K个元素也就是最大的K个，那我能不能只创建一个K大小的堆，其实完全可以，那大家想一下我是要创建一个大堆还是一个小堆呢？-------------小堆！为什么呢？举个例子假如你现在要找最大的前十个数，然后你创建了一个十个数字的大堆，现在堆顶是十个数里边最大的数，堆顶其实可以想象一个栈顶，他才是你对数据操作的关键位置，假如你创建的是大堆，也就是前十个数最大的在堆顶，那假如第十一个数比堆顶小，那你能证明什么呢？他该不该入堆呢？万一他比十个数字所有都小？那万一他只比堆顶元素小呢？但是你又不能把这个数和堆里所有元素都比较呢？所以你要创建一个小堆，堆顶是最小的元素，如果你接下来比较的数堆顶大，那就说明这个数要替代了堆顶的数了，当他替换堆顶元素之后进行一次向下调整，这时候堆里最小的元素又跑到堆顶了，只要比他大那就把它替换掉，当整个数组遍历完毕之后，堆里的元素就是最大的十个元素了。

  那我们应该如何在直接在数组上进行堆的一系列操作呢？

void HeapTopK(int *a, int n, int k)

{

int num = n;

int i= (k - 2) / 2;

for (; i >= 0; i--)

{

 

AdjustDown(a, k, i);

}

for (i = k; i < num; i++)

{

if (a[i]>a[0])

{

int temp = a[0];

a[0] = a[i];

a[i] = temp;

AdjustDown(a, k, 0);

}

}

for (i = 0; i < k; i++)

{

 

printf("%d\n", a[i]);

}

}

这里用到的向下调整函数我之前虽然有些过，但是，等下我还是会放在后边，方便大家看。

这里首先我在数组上的前K个数创建一个堆。

for (; i >= 0; i--)

{

 

AdjustDown(a, k, i);

}

其实这里和我们直接在堆数据结构进行操作是一样的，不过这里操作的是数组的前K个元素。

for (i = k; i < num; i++)

{

if (a[i]>a[0])

{

int temp = a[0];

a[0] = a[i];

a[i] = temp;

AdjustDown(a, k, 0);

}

}

 

然后通过第K个开始往后每个元素和堆顶进行比较，如果打的话就进行交换，交换之后一定要记着再次进行向下调整函数。才能保证交换之后的数组堆仍然是一个小堆，堆顶元素仍然可以进行比较。

 

#define _CRT_SECURE_NO_WARNINGS 1

 

#include<stdio.h>

#include<stdlib.h>

 

void AdjustDown(int *a, int n, int root)

{

int child = root * 2 + 1;

int parent = root;

while (child < n)

{

if ((child+1<n)&&(a[child + 1] < a[child]))

child++;

if (a[parent]>a[child])

{

int temp = a[child];

a[child] = a[parent];

a[parent] = temp;;

parent = child;

child = parent * 2 + 1;

}

else

break;

}

}

这是向下调整函数。

 

int main()

{

int arr[10] = { 1, 23, 43, 45, 65, 76, 78, 98, 90, 123 };

HeapTopK(arr, 10, 5);

system("pause");

return 0;

}

这是主函数进行测试的时候使用的。