堆排序详解

        堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
二叉树

特点：每个节点最多只有2个子节点（不存在度大于2的节点）
满二叉树

特点：叶子节点全部都在最底层；除叶子节点外，每个节点都有左右孩子；
完全二叉树
 
特点：叶子节点全部都在最底的两层；最后一层只缺少右边的叶子节点，左边一定有叶子节点；除了最后一层，其他层的节点个数均达到最大值；
最大堆和最小堆
最大堆：堆顶是整个堆中最大元素；
最小堆：堆顶是整个堆中最小元素；
算法思路：
        例如：无序数组：int arr[] = {4,2,8,0,5,7,1,3,9};既然用到堆，肯定先要将数组构建成二叉堆。需要对数组从小到大排序，则构建成最大(小)堆。
step1：初始化堆
        先来看看数组是如何存储二叉树的：

 
注意：这里考虑的当前节点，必须是完全二叉树的非叶子节点。并且节点的左孩子和

堆排序详解最先出现在Python成神之路。