我们在学习优先队列之前我们先来看看他和普通队列的区别
普通队列:先进先出,后进后出
优先队列:出队顺序和入队顺序无关,和优先级有关。动态选择优先级高的执行
不论是普通队列 还是优先队列,他们的本质还是一个队列 所以我们可以复用原来的队列的接口。我们也可以使用多种数据结构作为优先队列的底层实现结构,我们今天学的堆就是其中的一种底层实现结构。
二叉堆(堆本身就是一颗二叉树)
1.完全二叉树(把元素一层一层的放,知道放完为止)
2.堆中某个节点的值总是不大于其父亲节点的值(最大堆)
3…堆中某个节点的值总是不小于其父亲节点的值(最小堆)
用数组存储二叉堆
每个父亲节点的左孩子索引 = 父亲节点索引 * 2 +1;
每个父亲节点的右孩子索引 = 父亲节点索引 * 2 + 2;
每个父亲节点索引 = (孩子节点-1) / 2;
要注意该节点有没有父亲节点,具体的实现代码如下