堆是一种数组对象,它可以被视为一棵完全二叉树。
跟完全二叉树的区别
它只有大根堆(父亲节点>=儿子节点)和小根堆(儿子节点>=父亲节点)<--堆
和排序二叉树的区别是:排序二叉树是 左孩子<=父亲节点<=右孩子 <--非堆,单独成一种
不过,下面的内容和排序二叉树完全没有关系
独属于完全二叉树的存图方式
首先,逐个编号,接下来,挨个存图就行了~(太高贵了)
那怎么取节点呢?设父亲的编号为i,那么左孩子=2i,右孩子=2i+1,父亲节点就是左孩子 or 右孩子 /2
堆的两种操作
1、put:加入一个元素,原理就是每次和父亲节点比较,若自己大于父亲节点,他俩就交换,知道到达适合的位置
代码模板:
2、get:取出并删除一个元素,原理和put差不多,就是方向反一反。
代码模板:
优先队列和堆的关系