堆与优先队列：解决TopK问题的常用数据结构

# 1. 引言

## 介绍TopK问题及其在实际应用中的重要性

在数据处理和分析领域，TopK问题是指从一组元素中找出前K个最大或最小的元素的问题。在很多实际场景中，我们需要找出最高的K个销售额、最受欢迎的K个产品或最热门的K个新闻等。解决TopK问题不仅可以帮助我们快速找到重要的元素，还可以降低计算复杂度和减少资源消耗。

## 概述本文将介绍的两个常用数据结构：堆和优先队列

为了高效地解决TopK问题，本文将介绍两个常用的数据结构：堆和优先队列。堆是完全二叉树的一种特殊形式，它具有以下特性：
- 堆中的每个节点都大于等于（或小于等于）其子节点
- 堆总是完全填满，也就是说除了最后一层，其他层都是满的
- 堆可以分为最大堆和最小堆两种类型，分别用于解决TopK最大和TopK最小问题

优先队列是一种特殊的队列，它的每个元素都关联有一个优先级。具有较高优先级的元素在插入和删除过程中会被优先处理。优先队列的实现方式多种多样，其中一种常见的方式就是利用堆来实现。

接下来的章节中，我们将分别介绍堆和优先队列的基本概念、实现方式，并探讨它们在解决TopK问题中的应用。

# 2. 堆的基本概念与实现

堆是一种特殊的树形数据结构，具有以下性质：
- 在堆中，父节点的值总是大于等于/小于等于其子节点的值，根节点是堆中的最大/最小元素。
- 堆通常使用数组来实现，具体来说，堆是一个完全二叉树，可以使用数组来表示它，根节点索引为0，对于索引为 i 的节点：
- 其父节点索引为 (i-1)/2
- 其左子节点索引为 2*i+1
- 其右子节点索引为 2*i+2

堆的插入操作：
- 将新元素插入堆的末尾
- 通过上浮操作，将新元素上浮到合适的位置，以满足堆的性质

堆的删除操作：
- 删除堆顶元素
- 将堆的最后一个元素移到堆顶
- 通过下沉操作，将新的堆顶元素下沉到合适的位置，以满足堆的性质

下面是使用Python实现的堆插入和删除操作的示例代码：

class Heap:
    def __init__(self):
        self.data = []

    def insert(self, val):
        self.data.append(val)
        self.shift_up(len(self.data) - 1)

    def shift_up(self, idx):
        while idx > 0:
            parent = (idx - 1) // 2
            if self.data[parent] < self.data[idx]:  # max heap, use > for min heap
                self.data[parent], self.data[idx] = self.data[idx], self.data[parent]
                idx = parent
            else:
                break

    def extract_max(self):
        if not self.data:
            return None
        if len(self.data) == 1:
            return self.data.pop()

        max_val = self.data[0]
        self.data[0] = self.data.pop()
        self.shift_down(0)
        return max_val

    def shift_down(self, idx):
        length = len(self.data)
        while True:
            max_pos = idx
            left = 2 * idx + 1
            right = 2 * idx + 2
            if left < length and self.data[left] > self.data[max_pos]:  # max heap, use < for min heap
                max_pos = left