[编程基础]最小/大堆的实现

定义:1:一个完全二叉树,可以是空

2:子结点不能比父结点大/小

3:每一个结点的子树也是一个堆

知识点

1:二进制左移,右移。

2:完全二叉树,因为对应的树结点都是有两个叶结点。1:3,4;2:5,6;3:7,8;4:9,10,所以子结点的父结点都是除2得。对应的数字为当前数字-1右移一位。

(i - 1) >> 1;//找到i的跟结点
tmp << 1, (tmp << 1) + 1;//为tmp的左右子树

3:比较二叉树的大小。先从右子树对比树结点,如果大或者小,就和调换值;再用左子树和树结点比较。因为我们存值的时候是用从左到右这样存的。

4:添加值。添加到堆的最后,然后开始向上比较。

5:获取值。最大值or最小值,已经在root结点上,所以取走最上面的值就可以来;再把最后到值放到最顶部开始比较。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注