堆

#二叉树堆

• 堆是一棵==完全二叉树==，根据成立条件可分为大顶堆和小顶堆
  • 大顶堆的堆顶元素是最大的。
  • 小顶堆的堆顶元素是最小的。
• 优先队列的定义是具有出队优先级的队列，通常使用堆来实现。
• 堆的常用操作及其对应的时间复杂度包括：
  • 元素入堆 O(log⁡n)
  • 堆顶元素出堆 O(log⁡n) 
  • 访问堆顶元素 O(1) 等
• 完全二叉树非常适合用数组表示，因此我们通常使用数组来存储堆。
• 堆化操作用于维护堆的性质，在入堆和出堆操作中都会用到。
• 输入 n 个元素并建堆的时间复杂度可以优化至 O(n) ，非常高效。
• Top-k 是一个经典算法问题，可以使用堆数据结构高效解决，时间复杂度为 O(nlog⁡k) 。

数据结构的“堆”与内存管理的“堆”是同一个概念吗

• 两者不是同一个概念，只是碰巧都叫“堆”。