堆排序思维导图

堆介绍:底层逻辑是完全二叉树

完全二叉树

只有底层可以没达到最大节点数，但是底层的所有节点都是自左而右填充的

数组元素i对应到完全二叉树，找到数组元素的父节点和子节点在数组中的位置，i是数组元素的下标索引，0起算

数组元素i的左子节点在数组中的位置=2*i+1

数组元素i的右子节点在数组中的位置=2*i+2

数组元素i的父节点在数组中的位置=（i-1）/2，结果向下取整

数组元素的下标索引与完全二叉树的下标索引对应关系

数组元素的下标索引=完全二叉树的下标索引（两个下标索引都是0起算）

列外：数组元素和完全二叉树元素的下标位置1起算，主要是处理过程方便

数组元素i的左子节点在数组中的位置=2*i

数组元素i的右子节点在数组中的位置=2*i+1

数组元素i的父节点在数组中的位置=i/2

堆属性：大/小顶堆

底层对应的完全二叉树中，任一节点对应的子树中其根节点逻辑上是最大/小的，这是一种约束，必须要满足的条件

堆中新增堆元素

放在堆尾，然后根据堆属性约束完成堆化过程，主要是当前新增元素与其父元素的比较和位置交换

堆中弹出任意元素

将待弹出元素与堆尾元素A交换，然后根据堆属性完成另一种堆化过程，主要是判断A元素是否需要上浮或下沉，建议先比较其父元素判断是否上浮，否则走下沉流程

堆排序过程

1.堆化数组元素

方法1：基于完全二叉树，自下而上逐个处理每个节点，每个节点走下沉流程（已推敲）

方法2：基于完全二叉树，自上而下逐个处理每个节点，每个节点走上浮流程（未推敲）

2.逐个弹出堆顶元素