堆的常见应用2

        堆在解决 Top K 问题（即从海量数据中找出最大或最小的 K 个元素）中非常高效，核心思想是通过维护一个固定大小的堆结构，避免对全部数据进行排序，从而显著降低时间和空间复杂度。

一、Top K 问题的两种场景

1. 静态数据：数据已全部存储在内存或磁盘中。

2. 动态数据流：数据持续输入，需要实时维护 Top K 结果。

二、堆的两种应用策略

1. 找最大的 K 个元素 → 最小堆（Min-Heap）

• 核心思想：维护一个大小为 K 的最小堆，堆顶是当前 K 个元素中的最小值。

• 操作步骤：

  1. 初始化堆：将前 K 个元素直接插入最小堆。

  2. 遍历剩余元素：

     • 若当前元素 > 堆顶元素（即比当前 K 个中的最小值大）：

       •  替换堆顶元素。

       •  从堆顶向下调整（Heapify Down），恢复最小堆性质。

     • 否则跳过。

  3. 最终结果：堆中所有元素即为最大的 K 个元素。

• 时间复杂度：O(n log K)
  （每个元素最多进行一次堆调整，调整代价为 O(log K)）

2. 找最小的 K 个元素 → 最大堆（Max-Heap）

• 核心思想：维护一个大小为 K 的最大堆，堆顶是当前 K 个元素中的最大值。

• 操作步骤：

  1. 初始化堆：将前 K 个元素插入最大堆。

  2. 遍历剩余元素：

     • 若当前元素 < 堆顶元素（即比当前 K 个中的最大值小）：

       • 替换堆顶元素。

       • 从堆顶向下调整（Heapify Down），恢复最大堆性质。

     • 否则跳过。

  3. 最终结果：堆中所有元素即为最小的 K 个元素。

• 时间复杂度：O(n log K)

三、堆解决TOP K的优点： 

1. 空间效率：只需维护大小为 K 的堆，空间复杂度为 O(K)，适用于海量数据。

2. 时间效率：避免全排序（O(n log n)），只需 O(n log K) 时间。

3. 动态处理能力：支持数据流场景，逐个处理元素。

四、代码实现 （以找最大的 K 个元素为例）

最小堆的向下调整

// 最小堆的向下调整（维护堆性质）
void minHeapify(int *heap, int k, int i) {
    int smallest = i;        // 当前最小节点
    int left = 2 * i + 1;    // 左子节点
    int right = 2 * i + 2;   // 右子节点

    // 找到当前节点、左子、右子中的最小值
    if (left < k && heap[left] < heap[smallest])
        smallest = left;
    if (right < k && heap[right] < heap[smallest])
        smallest = right;

    // 若最小值不是当前节点，交换并递归调整
    if (smallest != i) {
        int temp = heap[i];
        heap[i] = heap[smallest];
        heap[smallest] = temp;
        minHeapify(heap, k, smallest);
    }
}

用最小堆找出前K大的元素

// 构建最小堆（从最后一个非叶子节点开始调整）
void buildMinHeap(int *heap, int k) {
    for (int i = k / 2 - 1; i >= 0; i--)
        minHeapify(heap, k, i);
}

// 用最小堆找出最大的K个元素
void findTopK(int *arr, int n, int k) {
    int *heap = (int *)malloc(k * sizeof(int));
    
    // 1. 初始化堆：取前K个元素
    for (int i = 0; i < k; i++) 
        heap[i] = arr[i];
    buildMinHeap(heap, k);  // 构建最小堆

    // 2. 遍历剩余元素
    for (int i = k; i < n; i++) {
        // 若当前元素比堆顶大，替换并调整
        if (arr[i] > heap[0]) {
            heap[0] = arr[i];
            minHeapify(heap, k, 0);
        }
    }

    // 输出结果
    printf("最大的 %d 个元素: ", k);
    for (int i = 0; i < k; i++)
        printf("%d ", heap[i]);
    printf("\n");

    free(heap);
}

五、与其他方法的对比

        全排序：简单但低效，适合小数据多次查询。

        快速选择：高效平均时间，适合单次查询且可修改数组。

        堆方法：平衡时间与空间，适合海量数据或动态数据流。

 这里简单实现快速选择的思路（基于快排实现）：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 交换两个元素
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数（降序分区）
int partition(int arr[], int left, int right) {
    int pivot_idx = left + rand() % (right - left + 1);
    int pivot = arr[pivot_idx];
    swap(&arr[pivot_idx], &arr[right]); // 将pivot移到末尾
    
    int i = left;
    for (int j = left; j < right; j++) {
        if (arr[j] >= pivot) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[right]); // 将pivot放回正确位置
    return i;
}

// 快速选择核心逻辑
void quick_select(int arr[], int left, int right, int k) {
    if (left >= right) return;
    
    int pos = partition(arr, left, right);
    if (pos == k) {
        return; // 找到第k大的元素，终止递归
    } else if (pos < k) {
        quick_select(arr, pos + 1, right, k); // 处理右半部分
    } else {
        quick_select(arr, left, pos - 1, k);  // 处理左半部分
    }
}

// 快速选择方法解决Top K（最大的K个元素）
void topk_quick_select(int arr[], int n, int k) {
    srand(time(NULL));
    quick_select(arr, 0, n - 1, k - 1); // 找到第k大的元素的位置
    
    // 输出前k个元素（注意：原数组已被部分修改）
    printf("快速选择结果: ");
    for (int i = 0; i < k; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}