数据结构之堆

Posted by Shen Chaoran on September 7, 2018

优先队列,类似于飞机登机时分为头等舱、商务舱、经济舱。

定义

  • 完全二叉树
  • 最大/小树

实现

用数组实现

  • 建堆:自底向上建堆。从最后一个非叶节点开始调整堆,每次调整保证了该叶节点的子树符合要求,所以最后的堆也符合要求。
  • 插入:插入到数组的最后,然后调整这个叶节点
  • 删除:
  • 调整:自顶向下调整堆

参考