【笔记】堆学习笔记

前言

数据结构之堆的学习笔记

堆的定义

• 堆实质上是一种特殊的树——完全二叉树

堆的特性

• 除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满

• 每个结点都大于等于它的两个子结点，但是这两个子结点的顺序并没有规定

公式

• 如果一个结点的位置为k

  • 则它的父结点的位置为k/2
  • 则它的两个子结点位置分别为2k和2k+1

• 这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树上移动

完成

参考文献

哔哩哔哩——黑马程序员