堆结构: 实质是数组
特点:以数组的形式去存储完全二叉树
原理:以前序遍历完全二叉树,得出结点的前序序列,以数组的形式存储该序列。
查找父,子结点通过数组下标ID间的转换关系实现。
优点:节省存储空间,查询效率高
缺点:1·只能表示完全二叉树(更广泛的可以说是完全n叉树)
2·对树的插入,删除操作执行效率低
3·事先必须知道树节点个数,以确定数组大小
联想:其优缺点都是由于其实现原理决定的,以特定的顺序遍历树节点,得出相应的序列,使得父子结点下标拥有固定的转换关系,从而省掉了指向父结点和子节点的指针变量,节省空间,提高查询效率。但是一但遍历的序列发生改变,位置发生改变的数据项就要移动到相应的位置,所以对于影响序列的插入,删除操作执行效率很差。由于数组的空间是固定的,对于插入操作的支持也是很有限的。