5-堆排序

5. 堆排序

  堆是指具有下列性质的完全二叉树     完全二叉树 i的双亲是[i/2]

         根节点一定最大或者最小 ！

         1 每个节点的值>=其左右节点的值   大顶堆

         2 每个节点的值<=其左右节点的值   小顶堆

        堆排序 Heap Sort  就是利用堆进行排序  如大顶堆。 将带排序的数列构造程一个大顶堆 然后将跟节点与堆数组末尾元素互换，然后将剩下的n-1个序列重新构造成堆  往返进行。

堆排序（Heap Sort）只需要一个记录元素大小的辅助空间（供交换用），每个待排序的记录仅占有一个存储空间。

堆的存储

　　一般用数组来表示堆，若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2*i+1和2*i+2。

　　（注：如果根结点是从1开始，则左右孩子结点分别是2i和2i+1。）

　　如第0个结点左右子结点下标分别为1和2。

　　如最大化堆如下：

 

　　左图为其存储结构，右图为其逻辑结构。

　　　1.如何由一个无序序列建成一个堆？

　　　2.如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

        堆排序方法对记录数较少的文件并不值得提倡，但对n较大的文件还是很有效的。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。

　　堆排序在最坏的情况下，其时间复杂度也为O(nlogn)。相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小的供交换用的辅助存储空间。

堆排的时间复杂度为O(n log n).    不稳定 

#include <iostream>
#include <cstring>
using namespace std;

void HeapAdjust1(int a[], int pos, int n)//这个不太好理解
{
    int temp = a[pos];
    int child = 2*pos+1;
    while(child<n)
    {
        if(child+1<n && a[child]<a[child+1])
        {
            child++;
        }
        if(a[pos]<a[child])
        {
            a[pos] = a[child];
            pos = child;
            child = 2*child+1;
        }
        else
        {
            break;
        }
    }
    a[pos] = temp;
}

void HeapAdjust(int a[], int pos, int n)
{
    int max = pos;
    int Left = 2*pos+1;
    int Right = 2*pos+2;
    if(pos<=(n-1)/2)
    {
        if(Left<n && a[max]<a[Left])
        {
            max = Left;
        }
        if(Right<n && a[max]<a[Right])
        {
            max = Right;
        }
        if(pos != max)
        {
            int temp =a[pos];
            a[pos] = a[max];
            a[max] = temp;
            HeapAdjust(a, max,n);//避免调整之后以max为父节点的子树不是堆
        }
    }

}
void BuildHeap(int a[], int n)
{
    for(int pos=(n-1)/2;pos>=0; --pos)
    {
        HeapAdjust(a,pos,n);
    }
}
void HeapSort(int a[], int n)
{
    BuildHeap(a, n);
    for(int len = n-1;len>0; --len)
    {
        int temp = a[len];
        a[len] = a[0];
        a[0] = temp;
        HeapAdjust(a, 0, len);
    }
}
int main()
{
    int a[9] = {9,1,5,8,3,7,4,6,2};
    //ShellSort(a, 9);
    HeapSort(a, 9);
    for(int i=0;i<9;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}