二叉堆是一种完全二叉树数据结构，具有以下特性：

• 最小堆：每个节点的值都小于或等于其子节点的值

• 最大堆：每个节点的值都大于或等于其子节点的值

二叉堆在计算机科学中有广泛的应用，主要得益于其高效的插入和删除操作（O(log n)时间复杂度）以及快速访问极值（O(1)时间复杂度）的特性。

最小堆和最大堆是部分有序的数据结构，而不是完全有序的。它们遵循特定的堆性质，但不同于完全排序的数组或列表。

1. 堆的性质

• 最小堆：每个节点的值都小于或等于其子节点的值

• 最大堆：每个节点的值都大于或等于其子节点的值

2. 有序性表现

• 层级有序：只保证父节点与子节点之间的关系，不保证兄弟节点之间的顺序

• 局部有序：从根节点到任意叶子节点的路径是有序的（最小堆递减，最大堆递增）

• 全局无序：不同分支上的节点没有顺序关系

最小堆示例：

       1
     /   \
    3     2
   / \   /
  4   5 6

• 满足父节点≤子节点

• 但兄弟节点3和2是无序的(3>2)

• 子树之间也无序(右子树2比左子树的4,5小)

最大堆示例：

       6
     /   \
    4     5
   / \   /
  3   2 1

• 满足父节点≥子节点

• 但兄弟节点4和5是无序的

• 子树之间也无序

Top K 问题是指从一个数据集中找出最大（或最小）的 K 个元素。二叉堆（特别是最小堆或最大堆）是解决这类问题的高效数据结构。

1. 使用最小堆解决 Top K 最大元素问题

步骤：

1. 初始化一个大小为 K 的最小堆

2. 遍历数据集中的每个元素：

   • 如果堆中元素数量小于 K，直接插入堆

   • 否则，比较当前元素与堆顶（最小元素）：

     • 如果当前元素 > 堆顶元素，替换堆顶元素并堆化

     • 否则跳过

3. 遍历完成后，堆中保存的就是最大的 K 个元素

python实现：

import heapq

def top_k_largest(nums, k):
    min_heap = []
    for num in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        else:
            if num > min_heap[0]:
                heapq.heappop(min_heap)
                heapq.heappush(min_heap, num)
    return min_heap

# 示例
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 3
print(top_k_largest(nums, k))  # 输出 [5, 6, 9]

java实现：

import java.util.PriorityQueue;

public class TopKLargest {
    public static int[] topKLargest(int[] nums, int k) {
        // 创建最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        
        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else {
                if (num > minHeap.peek()) {
                    minHeap.poll();
                    minHeap.offer(num);
                }
            }
        }
        
        // 将堆中的元素转换为数组
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        int k = 3;
        int[] result = topKLargest(nums, k);
        System.out.println("Top " + k + " largest elements:");
        for (int num : result) {
            System.out.print(num + " ");
        }
        // 输出: 5 5 6 9 (顺序可能不同，因为堆不保证顺序)
    }
}

2. 使用最大堆解决 Top K 最小元素问题

步骤：

1. 初始化一个大小为 K 的最大堆

2. 遍历数据集中的每个元素：

   • 如果堆中元素数量小于 K，直接插入堆

   • 否则，比较当前元素与堆顶（最大元素）：

     • 如果当前元素 < 堆顶元素，替换堆顶元素并堆化

     • 否则跳过

3. 遍历完成后，堆中保存的就是最小的 K 个元素

python实现：

import heapq

def top_k_smallest(nums, k):
    # Python的heapq模块只实现最小堆，所以用负数模拟最大堆
    max_heap = []
    for num in nums:
        if len(max_heap) < k:
            heapq.heappush(max_heap, -num)
        else:
            if num < -max_heap[0]:
                heapq.heappop(max_heap)
                heapq.heappush(max_heap, -num)
    return [-x for x in max_heap]

# 示例
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 3
print(top_k_smallest(nums, k))  # 输出 [1, 1, 2]

java实现：

import java.util.PriorityQueue;
import java.util.Collections;

public class TopKSmallest {
    public static int[] topKSmallest(int[] nums, int k) {
        // 创建最大堆（使用Collections.reverseOrder()）
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, Collections.reverseOrder());
        
        for (int num : nums) {
            if (maxHeap.size() < k) {
                maxHeap.offer(num);
            } else {
                if (num < maxHeap.peek()) {
                    maxHeap.poll();
                    maxHeap.offer(num);
                }
            }
        }
        
        // 将堆中的元素转换为数组
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = maxHeap.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        int k = 3;
        int[] result = topKSmallest(nums, k);
        System.out.println("Top " + k + " smallest elements:");
        for (int num : result) {
            System.out.print(num + " ");
        }
        // 输出: 1 1 2 (顺序可能不同)
    }
}