堆排序

  堆排序是一种树形选择排序，是对直接选择排序的有效改进。n个关键字序列Kl,K2,…，Kn称为堆，当且仅当该序列满足（Ki≤K2i且Ki≤K2i+1）或（Ki≥K2i且Ki≥K2i+1），（1≤i≤ ）。

小根堆：根结点 （堆顶）的关键字是堆里所有结点关键字中最小者，称为小根堆；
大根堆：根结点的关键字是堆里所有结点 关键字中最大者，称为大根堆。
  若将此序列所存储的向量R[1…n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树，即树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点 的关键字。

  堆排序的关键步骤有两个，一是如何建立初始堆；二是当堆的根结点与堆的最后一个结点交换后，如何对少了一个结点后的结点序列做调整，使之重新成为堆。 下面，我们通过一个例子来具体说明建立初始堆和调整堆的过程。

  假设关键字序列为 {42,13,24,91,23,16,05,88},
首先将关键字按顺序放入一个空的完全二叉树中，
其次将其调整成大跟堆

在初始堆的基础上，把第一个元素（91）和最后一个元素（13）交换，输出91.

因13小于其左右子结点88和24,则和88交换，交换后，13还小于其 左右子结点42和23,则和42再交换。
把第一个元素（88）和最后一个元素（05）交换，输出88.

以此类推，





堆排序的最坏时间复杂度为O（nlog2n）