堆是什么

堆是一种用完全二叉树表示的数据结构，其特点是父节点比子节点大（若是大顶堆，以下若无特殊说明均指大顶堆）

堆排序算法

堆排序算法是利用堆的性质进行排序的一种算法，其大致的原理是，把待排序数组先建立成一个大顶堆， 然后把最后一个节点和第一个节点交换，把交换后的最后一个节点从堆中剔除，此时从堆顶开始，若根节点小于它最大的子节点，就跟这个子节点换位（根节点下沉，子节点上升，即保持父节点大于子节点的性质），此时再把下沉下来的根节点看作是所在子树的根节点，重复刚刚的步骤直到堆的末尾，这样就完成了堆排序。 具体代码如下：

/*  输入：数组A，堆的长度hLen，以及需要调整的节点i  功能：调堆*/void AdjustHeap(int A[], int hLen, int i){    int left = LeftChild(i);  //节点i的左孩子    int right = RightChild(i); //节点i的右孩子节点    int largest = i;    int temp;    while(left < hLen || right < hLen)    {        if (left < hLen && A[largest] < A[left])        {            largest = left;        }        if (right < hLen && A[largest] < A[right])        {            largest = right;        }        if (i != largest)   //如果最大值不是父节点        {            temp = A[largest]; //交换父节点和和拥有最大值的子节点交换            A[largest] = A[i];            A[i] = temp;            i = largest;         //新的父节点，以备迭代调堆            left = LeftChild(i);  //新的子节点            right = RightChild(i);        }        else        {            break;        }    }}/*  输入：数组A，堆的大小hLen  功能：建堆*/void BuildHeap(int A[], int hLen){    int i;    int begin = hLen/2 - 1;  //最后一个非叶子节点    for (i = begin; i >= 0; i--)    {        AdjustHeap(A, hLen, i);      }}/*  输入：数组A，待排序数组的大小aLen  功能：堆排序*/void HeapSort(int A[], int aLen){    int hLen = aLen;    int temp;    BuildHeap(A, hLen);      //建堆    while (hLen > 1)    {         temp = A[hLen-1];    //交换堆的第一个元素和堆的最后一个元素         A[hLen-1] = A[0];         A[0] = temp;         hLen--;        //堆的大小减一         AdjustHeap(A, hLen, 0);  //调堆    }}

算法效率

最好或者最坏情况下，堆排序的运行时间都是O(nlogn)