问题描述
记得刚学习数据结构的时候,就容易混淆二叉堆和二叉搜索树,其实虽说堆也是一种完全二叉树,但二者差别还是挺大的,本文试做分析。
逻辑结构二叉堆和二叉搜索树都是结点带权重,并在父子结点间满足某种规则的数据结构。
二叉堆是一种完全二叉树,分大根堆、小根堆两种,子结点总是大于或小于父结点。 大根堆,顾名思义,根是最大的,每个子结点都要小于父结点,不区分左右儿子谁大谁小,也不必保证某个“孙子结点”一定要小于另一个“儿子结点”。 小根堆恰恰相反,根是最小的,每个子结点都要大于父结点,不区分左右儿子谁大谁小,也不必保证某个“孙子结点”一定要大于另一个“儿子结点”。
二叉搜索树是一种特殊的二叉树,左儿子结点小于父结点,右儿子结点大于父结点。 所谓的AVL树、红黑树等复杂一些的树状数据结构,很多都是二叉搜索树优化得到的。
存储结构二叉堆和二叉搜索树看似都是“树”,实则在存储结构上差别很大。
我们也知道,顺序存储和链接存储是两种基本的存储结构。顺序存储减少了指针等的额外空间浪费,没有结点这个问题,却在某个元素的增删后的调整上很麻烦,且必须在内存中连续分配;链接存储反是。
由于二叉堆是一种完全二叉树,所以可以按照 id 编号,通过数组存取,更好的是用顺序表(Java党参考java.util.ArrayList,C++党参考STL-vecter),根据 id 访问父结点或子结点,既节约了指针空间的结构性开销,也