二叉搜索树VS小顶堆
左子树中所有节点的值<父节点的值<右子树中所有节点的值;
小顶堆是父节点的值<=左/右子树中所有节点的值;
关键区别总结
性质 | 二叉搜索树(BST) | 小顶堆(Min-Heap) |
---|---|---|
节点关系 | 左 < 父 < 右 | 父 ≤ 左子 且 父 ≤ 右子 |
左右子节点关系 | 左子节点 < 右子节点(因左 < 父 < 右) | 左子节点和右子节点无明确大小关系 |
结构目的 | 快速搜索、插入、删除(O(log n)) | 快速获取最小值(O(1)) |
是否完全二叉树 | 不一定 | 通常实现为完全二叉树(数组存储) |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Min的博客!
评论