堆，可以被看做一颗完全二叉树的数组对象。我们的数据实际上在逻辑上可以根据数组的索引构建出一颗完全二叉树。
堆排序是根据堆的这种数据结构设计的一种排序。假想一种常见的场景，操场上小伙伴们四散开来到处都是。突然要紧急集合，小伙伴们同时冲向同一个队列，但这时大家互相不熟悉，没有固定位置，又要赶紧按照高矮顺序排好队伍；有的小伙伴还有特殊能力，长高或者变矮，
要求队伍始终是按照高矮排好的。堆就是这样的一种优秀的数据结构，在每次添加或者修改元素时，都可以自动调整自身的结构，使其重新成为一个大根堆或者小根堆。而且，这个过程只要付出logN的代价（树的高度）。在大样本的情况下优势很大。
什么是大根堆和小根堆
每个节点的值都大于其左孩子和右孩子的值，称为大根堆；每个节点的值都小于其左孩子和右孩子的值，称为小根堆，如图。
对上边的每个数都进行标记，将二叉树映射成数组，就变成如下。
结点位置与索引值之间的关系
如果已知某个数的索引i，则i与结点的位置关系如下。
i位置结点的左孩子在数组中的位置是： (2*i) + 1
i位置结点的右孩子在数组中的位置是： (2*i) + 2
i位置结点的父节点在数组中的位置是： (i-1) / 2
yo peace！
网友评论