给定数组
a[m]，寻找最大的
n 个数：
- 如果
m <= n，则完成。
当 m 明显大于 n 时：成本为 O(m * log(n))。
形成一个 二叉优先队列 p[n]。插入的时间复杂度为 O(log(n))，删除的时间复杂度为 O(log(n))，查看最小值的时间复杂度为 O(1)。
迭代 a[]，当 a[i] 大于 p[] 中的最小值时，删除最小值并添加 a[i]。
否则，使用成本为 O(m * log(m)) 的简单排序 a[]
一些代码供OP开始使用：（扫描错误检查不充分，未经优化。）
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static void pq_enqueue(size_t current_size, int *pq, int value) {
size_t child = current_size;
while (child > 0) {
size_t parent = (child + 1) / 2 - 1;
if (pq[parent] <= value) {
break;
}
pq[child] = pq[parent];
child = parent;
}
pq[child] = value;
}
static int pq_dequeue(size_t current_size, int *pq) {
int v = pq[0];
size_t root = 0;
for (;;) {
size_t lchild = (root + 1) * 2 - 1;
size_t rchild = (root + 1) * 2 + 1 - 1;
if (lchild >= current_size) {
break;
}
int lvalue = pq[lchild];
int rvalue = rchild < current_size ? pq[rchild] : INT_MAX;
if (lvalue <= rvalue) {
pq[root] = lvalue;
root = lchild;
} else {
pq[root] = rvalue;
root = rchild;
}
}
if (root + 1 < current_size) {
pq[root] = pq[current_size - 1];
size_t child = root;
int value = pq[root];
while (child > 0) {
size_t parent = (child + 1) / 2 - 1;
if (pq[parent] <= value) {
break;
}
pq[child] = pq[parent];
child = parent;
}
pq[child] = value;
}
return v;
}
static clock_t test_pq(size_t n, int buf[n], size_t top_n) {
clock_t c0 = clock();
for (size_t i = 0; i < n; i++) {
buf[i] = rand();
}
int top[top_n];
for (size_t i = 0; i < top_n; i++) {
pq_enqueue(i, top, buf[i]);
}
for (size_t i = top_n; i < n; i++) {
if (buf[i] >= top[0]) {
pq_dequeue(top_n--, top);
pq_enqueue(top_n++, top, buf[i]);
}
}
long long sum = 0;
for (size_t i = 0; i < top_n; i++) {
if (i < 3) {
;
}
sum += top[i];
}
clock_t c1 = clock();
printf("n:%11zu, top_n:%5zu, sum: %15lld ticks:%9lld\n", n, top_n, sum,
(long long) (c1 - c0));
return c1 - c0;
}
int main() {
printf("RAND_MAX:%d\n", RAND_MAX);
size_t N = 1000000000;
int *buf = malloc(sizeof *buf * N);
if (buf) {
for (size_t n = 1000000; n <= N; n *= 10) {
test_pq(n, buf, 3);
}
for (size_t t = 4; t <= 1000; t *= 4) {
test_pq(N, buf, t);
}
free(buf);
}
return 0;
}
输出
RAND_MAX:2147483647
n: 1000000, top_n: 3, sum: 6442444824 ticks: 16
n: 10000000, top_n: 3, sum: 6442450334 ticks: 78
n: 100000000, top_n: 3, sum: 6442450883 ticks: 797
n: 1000000000, top_n: 3, sum: 6442450934 ticks: 7891
n: 1000000000, top_n: 4, sum: 8589934585 ticks: 6610
n: 1000000000, top_n: 16, sum: 34359737961 ticks: 6593
n: 1000000000, top_n: 64, sum: 137438948345 ticks: 6610
n: 1000000000, top_n: 256, sum: 549755742014 ticks: 6578
请注意，数组大小增加10倍时，时间也增长10倍。
当前N增加4倍时，时间不增长，因为对于随机数据而言，几乎所有值都小于前几个并且没有遇到增长代价。所以我想这是一个不好的测试用例来演示在O(n * log(top_n))中的log(top_n)。当top_n远小于n且为随机数据时，我们会接近O(n)。嗯，稍后再审查一下。
