数据结构:堆

堆的基础概念

  1. 堆的实质其实是二叉树
  2. 这棵二叉树除了叶子之外的所有节点都是“满”的
  3. 最后一层叶子节点也是有要求的,要求叶子节点都靠左对齐
  4. 满足这些条件的二叉树称为完全二叉树(complete binary tree)
  5. 堆是完全二叉树,但不是所有的完全二叉树都是堆,堆还有一个特殊的性质,就是大小的传递性
  6. 堆根据大小传递性的不同分为 大顶堆 和 小顶堆
  7. 大顶堆就是堆顶的元素也就是树根的元素是最大的。如果是小顶堆则相反,堆顶元素是最小的
  8. 传递性很好理解,就是所有节点的值大于/小于它两个孩子的值
  9. 堆的巧妙点在于,可以用数组来存储这个结构,而不需要自己建树
  10. 所谓建堆的过程,其实就是将元素一个一个插入堆当中的过程
  11. 堆和其他数据结构不同,它对于数据的查询非常有限,只允许查询堆顶的元素
  12. 同样也只允许删除堆顶的元素,删除堆顶的元素称为“弹出”(pop)