企业网站建设的心得,国家最新防疫政策,广告设计培训班,如何提高网站收录数TOP-K问题
TOP-K问题#xff1a;即求数据结合中前K个最大的元素或者最小的元素#xff0c;一般情况下数据量都比较大
比如#xff1a;专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等 对于Top-K问题#xff0c;能想到的最简单直接的方式就是排序#xff0c;但是…TOP-K问题
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大
比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。 举个例子 有十亿个整形数据我们的内存时4G也就是102410241024*8个字节的空间十亿个整形数据需要的是40亿个字节的空间就占了内存的一半空间这是不可行的
最佳的方式就是用堆来解决基本思路如下
用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素
下面我们进行代码的实现 首先我们生成1000个随机数范围再十万以内放入一个数组中
srand(time(0));
int* a (int*)malloc(sizeof(int) * 1000);
if (a NULL)
{perror(malloc);return 0;
}
for (size_t i 0; i 1000; i)
{a[i] rand() % 100000;
}然后我们随机将数组中的任意k个元素改为超过十万的数字方便验证
a[7] 100000 1;
a[49] 100000 2;
a[123] 100000 3;
a[456] 100000 4;
a[789] 100000 5;我们还要用到向下调整算法以便于建堆
void swap(int* p1, int* p2)
{int temp *p1;*p1 *p2;*p2 temp;
}
void AdjustDown(int* a, int n, int parent)
{int child (parent * 2) 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){swap(a[child], a[parent]);parentchild;child parent * 2 1;}else{break;}}
}最后我们将a数组中的前k个元素插入到top_k函数的数组里然后进行一次向下调整算法将其调整为大堆然后再用剩下的n-k个元素与堆顶元素进行比较如果比他大进替换进堆然后进行向下调整
void top_k(int* a, int n, int k)
{int i 0;int* top (int*)malloc(sizeof(int) * k);if (top NULL){perror(malloc);return;}for (i 0; i k; i){top[i] a[i];}for (i (k - 1 - 1) / 2; i 0; i--){AdjustDown(top, k, i);}for (i k; i 1000; i){if (a[i] top[0]){top[0] a[i];AdjustDown(top, k, 0);}}完整代码如下
#includestdio.h
#includestdlib.h
#includetime.h
#includeassert.h
void swap(int* p1, int* p2)
{int temp *p1;*p1 *p2;*p2 temp;
}
void AdjustDown(int* a, int n, int parent)
{int child (parent * 2) 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){swap(a[child], a[parent]);parentchild;child parent * 2 1;}else{break;}}
}
void top_k(int* a, int n, int k)
{int i 0;int* top (int*)malloc(sizeof(int) * k);if (top NULL){perror(malloc);return;}for (i 0; i k; i){top[i] a[i];}for (i (k - 1 - 1) / 2; i 0; i--){AdjustDown(top, k, i);}for (i k; i 1000; i){if (a[i] top[0]){top[0] a[i];AdjustDown(top, k, 0);}}for (i 0; i k; i){printf(%d , top[i]);}free(top);
}
int main()
{srand(time(0));int* a (int*)malloc(sizeof(int) * 1000);if (a NULL){perror(malloc);return 0;}for (size_t i 0; i 1000; i){a[i] rand() % 100000;}a[7] 100000 1;a[49] 100000 2;a[123] 100000 3;a[456] 100000 4;a[789] 100000 5;int k 5;top_k(a, 1000, k);
}向上调整算法和向下调整算法的时间复杂度
因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个节点不影响最终结果) 我们令高度为h节点个数n就等于2^(h)-1个 那么在向上调整算法中 最坏情况下最后一层的节点需要向上移动h-1次依次类推就得到总次数的表达式然后再用错位相减法和n和h的关系就能求出时间复杂度fn了 在向下调整算法中 最坏情况下倒数第二层节点向下只移动一次第一层最多移动h-1次
总结下来我们就会发现向上调整算法中是多节点乘多层数的关系而向下调整算法则是多节点乘少层数的关系我们进行比较就会发现其实向下调整算法的效率更高所以在平常的排序和建堆中我们 最常用的还是向下调整算法 向上调整算法的时间复杂度为
n*log(n)向下调整算法的时间复杂度为
log(n)因此向下调整算法的效率是远大于向上调整算法的 好了今天的分享到这里就结束了谢谢大家的支持
