算法之堆排序

痛定思痛，终于决定花半年时间深入学习技术面试题，为明年的跳槽作准备。以后会把比较重要且深刻掌握的知识点记录下来，加深理解及方便学习。

今天整理的算法是堆排序，这是我花费了一天的时间才吸收到的精华。下面按照我的理解整理了堆排序的算法思想。希望能让大家一目了然。

第一：给出一个无序队列或者数组

第二：建堆---把无序数组变为大根堆或者小根堆（大根堆：父节点的值大于任意子节点的值；小根堆：父节点的值小于子节点的值）以下按照建大根堆思想描述

1.从最后一个有子节点的父节点开始调整，此处的索引值为i=n/2-1

2.比较此处父节点和子节点的值大小，把最大值的节点调整值父节点

3.依次i--找出歌父节点和相应子节点的最大值，并把最大值调整至顶堆

4.经过上面的处理后就形成了一个大根堆，最大值在顶堆

第三：顶堆和最后一个子节点交接，再从堆中剔除最后一个子节点

第四：依次比较剔除后的堆中的父节点和子节点的最大值，交换位置，把最大值调整至顶堆

第五：循环第三和第四的步骤，最后输出一个小根堆，即按照从小到大的顺序

由于时间问题来不及画图，明天会增加图纸说明方便读懂