8.堆与堆的构建

1.堆的概述

  • 堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。它的特点是父节点的值大于（小于）两个子节点的值（分别称为大顶堆和小顶堆）。


    大顶堆

    小顶堆

2.堆的构建

  • 给定n个数，从n/2个节点开始，依次构建堆，直到第一个节点。
  • 举例：
    给定数组{5,23,37,41,59,16,23}，构建其大根树。

    1. 转换成树结构


    2. 从n/2节点开始，如图为3——"37"，构建其为堆。
    3. 现在轮到2，如图为"23"，构建其为堆。
    4. 现在轮到1，如图为"5",构建其为堆。

    5. 堆构建成功，存入数组顺序为：


最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容