算法-topK

完整算法，C语言版本：

#include <stdio.h>
#include <string.h>

#define K 10
#define NAME_LEN 50

// 一条热搜
typedef struct {
char name[NAME_LEN];
int hot; // 热度
} HotItem;

// ==============================
// 交换两个热搜
// ==============================
void swap(HotItem *a, HotItem *b)
{
HotItem temp = *a;
*a = *b;
*b = temp;
}

// ==============================
// 最小堆：向上调整
//
// 新元素放到堆末尾后，
// 如果比父节点小，就不断往上交换。
// ==============================
void heapUp(HotItem heap[], int index)
{
while (index > 0)
{
int parent = (index - 1) / 2;

// 已满足最小堆性质
if (heap[parent].hot <= heap[index].hot)
break;

swap(&heap[parent], &heap[index]);

index = parent;
}
}

// ==============================
// 最小堆：向下调整
//
// 堆顶被替换后，需要重新恢复最小堆。
// ==============================
void heapDown(HotItem heap[], int size, int index)
{
while (1)
{
int left = index * 2 + 1;
int right = index * 2 + 2;
int smallest = index;

// 找出：自己、左孩子、右孩子
// 三者中热度最小的
if (left < size &&
heap[left].hot < heap[smallest].hot)
{
smallest = left;
}

if (right < size &&
heap[right].hot < heap[smallest].hot)
{
smallest = right;
}

// 自己已经最小，不需要调整
if (smallest == index)
break;

swap(&heap[index], &heap[smallest]);

index = smallest;
}
}

// ==============================
// 处理一条新的热搜
// ==============================
void addHotItem(HotItem heap[],
int *size,
HotItem item)
{
// 情况1：Top10 还没有装满
if (*size < K)
{
heap[*size] = item;

heapUp(heap, *size);

(*size)++;
}

// 情况2：
// Top10 已经满了
// 新热搜比当前第10名还热
else if (item.hot > heap[0].hot)
{
// 淘汰当前 Top10 中最弱的
heap[0] = item;

// 恢复最小堆
heapDown(heap, *size, 0);
}

// 情况3：
// item.hot <= heap[0].hot
//
// 连当前第10名都打不过
// 直接丢弃即可
}

// ==============================
// 最终为了漂亮输出，
// 将 Top10 按热度从高到低排序
// K只有10，所以简单排序即可
// ==============================
void sortResult(HotItem arr[], int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (arr[j].hot > arr[i].hot)
{
swap(&arr[i], &arr[j]);
}
}
}
}

int main()
{
HotItem data[] = {
{"AI", 95},
{"世界杯", 80},
{"电影", 35},
{"天气", 20},
{"机器人", 88},
{"股票", 60},
{"游戏", 72},
{"手机", 45},
{"旅游", 55},
{"高考", 91},
{"汽车", 30},
{"音乐", 67},
{"芯片", 99},
{"航天", 76},
{"新能源", 83},
{"程序员", 50},
{"C语言", 86},
{"算法", 93}
};

int n = sizeof(data) / sizeof(data[0]);

// 最小堆
HotItem heap[K];

int heapSize = 0;

// 扫描所有热搜
for (int i = 0; i < n; i++)
{
addHotItem(
heap,
&heapSize,
data[i]
);
}

// 此时 heap 中就是 Top10
// 但堆本身不是从大到小排列的
sortResult(heap, heapSize);

printf("======= 热搜 Top 10 =======\n");

for (int i = 0; i < heapSize; i++)
{
printf(
"Top %2d %-15s 热度：%d\n",
i + 1,
heap[i].name,
heap[i].hot
);
}

return 0;
}