堆排序属于数据结构的经典算法之一

堆排序

核心理念：减治算法。借助堆结构实现数据选取，若需升序排列则构建最大堆，若需降序排列则构建最小堆

首先，此处简要说明二叉堆的基本概念：二叉堆在逻辑层面可以被看作是一种完全二叉树结构，在物理存储上则采用数组形式。其本质特性在于，对于任意一个节点而言，根节点的值应大于等于（在最大堆的情形下）所有子节点的值。该结构的主要功能是用于快速获取数据集中的极值。

堆排序主要分为以下三部分：

1.向下调整策略分析

• 前提条件：仅存在一个节点可能不符合堆结构的要求，而其余所有节点均符合堆的特性
  • 1.判断当前需要调整的节点是否为叶子节点（若其左子树的索引超出范围，则表明该节点为叶子节点）
  • 2.确定其子节点中数值最大的一个（若不存在右子树，则左子树即为最大子节点；若同时存在左右子树，则比较两者后选择数值较大的那个）
  • 3.将父节点的值与最大子节点的值进行对比，若父节点的值较大，则调整过程结束；反之则交换二者数值，并以新的节点位置为基础继续向下进行调整

2.建堆

构建整棵树的堆结构时，需确保其左右子树已满足堆的性质，并对根节点进行向下调整操作。具体步骤为：从最后一个非叶子节点开始，依次向前至索引0的位置，逐个执行向下调整过程。

3.堆排序算法解析

• 1.构建一个大型堆结构