一句话答案

堆是完全二叉树（大顶堆父≥子），插入/删除 O(logn)，建堆 O(n)；Java PriorityQueue 默认小顶堆。

核心要点

操作： 插入 O(logn) 上浮 / 删除堆顶 O(logn) 下沉 / 建堆 O(n)

Java： new PriorityQueue<>() 小顶堆，new PriorityQueue<>(Comparator.reverseOrder()) 大顶堆

应用： Top-K / 合并K个有序链表 / 中位数(大+小顶堆) / Dijkstra

追问与易错

追问方向：

• 大顶堆和小顶堆怎么选？
• 堆排序为什么不如快排常用？
• Java PriorityQueue 是线程安全的吗？

易错点：

• ❌ 堆就是完全排序的——堆只保证堆顶最大/最小
• ❌ PriorityQueue 是线程安全的——不是需要 PriorityBlockingQueue

💡 记忆锚点

堆像一棵"老大在上"的完全二叉树：大顶堆每个爸爸都比儿子大（堆顶最大），小顶堆反过来。新元素从底部"上浮"到合适位置，删堆顶后末尾补上再"下沉"，都是O(logn)。Java的PriorityQueue默认小顶堆（poll出来最小的），Top-K大用小顶堆（堆顶当门槛），合并K个有序链表也靠它。