怎么判断一个序列是不是堆?

2021年9月6日 3点热度 0条评论 来源: 拭心

已知一个序列,比如{100,6070,50,32,65},怎么判断是不是堆?

答案:把这个序列看成数组型的二叉树,如果根结点是i,左子树是2*i,右子树是2*i+1。

堆分为最大堆与最小堆。

  1. 最大堆中所有父节点都比左子树、右子树大,比如已知序列,画成堆就是:

    所以已知序列是个最大堆。

  2. 最小堆中所有父节点都比左子树、右子树小,比如{32,50,60,70,100,65},画成堆:

符合以上两种情况的序列就是堆

    原文作者:拭心
    原文地址: https://blog.csdn.net/u011240877/article/details/47706923
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。