TS数据结构与算法之堆有什么特点,和二叉树有什么关系

2022-03-10  本文已影响0人  子十一刻

堆栈模型

堆是一种特殊的完全二叉树。所有父结点都比子结点要小的完全二叉树我们称为最小堆。反之,如果所有父结点都比子结点要大,这样的完全二叉树称为最大堆。

逻辑结构 VS 物理结构

完全二叉树中父亲和儿子之间有着神奇的规律,我们只需用一个一维数组就可以存储完全二叉树。

         10
       /    \
      /      \
     14       25
    /  \     /  \
   33   81  82  99

上图是一个堆(从小到大),物理结构可以用数组表示为:

// 忽略0节点
const heap = [-1, 10, 14, 25, 33, 81, 82, 99];

数据之间的节点关系可以按二叉树的逻辑结构使用如下公式查找:

const parentIndex = Math.floor(i / 2);
const leftIndex = 2 * i;
const rightIndex = 2 * i + 1;

如:数据14对应数组下标为2,则父节点索引就是 2/2 = 1,对应数据为10;左子节点索引是 2*2=4 就是33; 右子节点索引是 2*2+1=5 就是81。

堆 VS BST

堆的使用场景

小结

上一篇 下一篇

猜你喜欢

热点阅读