堆

  • 粗略的理解了下，这个需要配合完全二叉树进行理解
  • 世人皆知，二叉树，每层个数呈现指数递增，第一层 1 第二层 2 第三层 4 第四层 8...
  • 将完全二叉树按层存入数组中，则是堆的原始形态，但此时并不符合堆的定义
  • ==关于数组位置和二叉树中的元素映射：数组地址位取 i=1,2,3,4....==
  • {
  • i 的父节点：i/2
  • i 的左孩子节点：2i
  • i 的右孩子节点: 2i+1
  • }
  • 堆分为
  • 大根堆：
  • 数组在完全二叉树中，需要找到所有的非终端节点，进行遍历
  • 实际上也很简单，只需要找到最后一个非终端节点即可，也就是数组长度的一半处，即是最后一个非终端节点
  • 在此处进行倒序遍历，直到遍历到首部
  • 每次遍历都需要保证该非终端节点的左右子节点均小于自己，如果不是，则选取最大的子节点进行交换
  • 每次遍历完成交换完成后，若是出现新的冲突则按照惯例继续交换，直到符合原则
  • 最后，这便是大根堆
  • 小根堆
  • 小根堆和大根堆的原理类似，原则变成左右节点均大于自己

    • 上述建堆过程的时间复杂度为O(n)

    计算量微大记住结论即可

    #堆的删除和插入

  • 以大根堆为例子
  • 删除堆顶元素，则末尾元素进入堆顶，然后再进行大根堆建立
  • 插入元素，将元素插入末尾，然后进行大根堆建立，记住是从下往上扫描