二叉堆

二叉堆是优先队列很普遍的一种实现，它又分为最小堆最大堆，最小堆和最大堆都是完全二叉树。
其结构体定义如下：

struct HeapStruct {
    int Capacity;    //堆的最大容量
    int Size;         //堆的当前结点数
    ElementType *Elements;   //存放堆结点的数组
}

typedef struct HeapStruct *PriorityQueue;

二叉堆的结点可以保存在一个数组中。
1、如果从数组的索引1开始存放堆结点，那么对于数组中任意位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的单元(2i + 1)中
2、如果从数组的索引0开始存放堆结点，那么对于数组中任意位置i上的元素，其左儿子在位置(2i+1)上，右儿子在左儿子后的单元(2i+2)中。

在下面的代码中，统一采用第一种方式存放堆结点。你可以通过下面的代码注意到，用第一种方式给编程带来的好处。

最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

（1）插入操作Insert，采用制造“空穴”，上滤的方式——“空穴”在堆中不断上移直到找出正确的位置。插入操作复杂度O(logN)。

void Insert(ElementType X, PriorityQueue H) {
    int i;

    if( IsFull(H) ) {      //判断堆是否已满
        Error( "Priority queue is full" );
        return ;
    }

    for( i = ++ H->Size; H->Elements[i/2] > X; i = i/2) {
        H->Elements[i] = H->Elements[i/2] ; 
    }
    H->Elements[i] = X ;
}

（2）删除最小元素(即根�结点)DeleteMin，下滤的方式。删除最小元素操作的复杂度O(logN)，因为删除后涉及重建堆。

ElementType DeleteMin(PriorityQueue H) {
    int i, Child ;
    ElementType MinElement, LastElement;

    if( IsEmpty(H) ) {        //判断堆是否为空
        Error( "Priority queue is empty" );
        return H->Elements[0];
    }
    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--]; //在�根结点删除了第一个堆结点，因此在根结点制造了一个“空穴”，
先保存最后一个堆结点，堆大小减1。下面的�代码是把LastElement放到合适的地方。

    for( i =1; i*2 <= H->Size; i= Child) {  //下滤过程
        
        //找较小的一个儿子结点
        Child = i * 2;            //左儿子结点
        if(Child != H->Size && H->Elements[Child + 1] < H->Elements[Child] )
            Child++;               //如果左儿子不是新堆的最后一个结点，且左儿子大于右儿子，我们选择右儿子
        
        //判断较小的儿子结点是否小于LastElement。若是，把该较小的儿子结点上移到自己的父结点；
        //若不是，退出循环。（即LastElement比儿子结点都小，可以作为它们的父结点插入）
        if(LastElement > H->Elements[Child] ) 
            H->Elements[i] = H->Elements[Child];
        else
            break;
    }
    H->Elements[i] = LastElement ; 
    return MinElement;    //返回被删除的根节点
}

（3）如果仅仅是�要获得最小值，那么可以在常数时间完成O(1)。

</br>

最大堆：父结点的键值总是�大于或等于任何一个子节点的键值。

（1）插入操作Insert，采用制造“空穴”，上滤的方式——“空穴”在堆中不断上移直到找出正确的位置。插入操作复杂度O(logN)。

void Insert(ElementType X, PriorityQueue H) {
    int i ;
    
    if( IsFull(H) ) {
        Error( "Priority queue is full" );
        return ;
    }

    for(i=++H->Size; H->Elements[i/2] < X; i = i/2) {
        H->Elements[i] = H->Elements[i/2];
    }
    H->Elements[i] = X;
}

对比最小堆的插入操作，可看到只是把for循环的条件">X"改为"<X"。意思是只要X比它的父结点大，就一直上滤。

（2）删除最大元素(即根�结点)DeleteMax，下滤的方式。删除最大元素操作的复杂度O(logN)，因为删除后涉及重建堆。

ElementType DeleteMax(PriorityQueue H) {
    int i, Child;
    ElementType MaxElement, LastElement;

    if( IsEmpty(H) ) {
        Error( "Priority queue is empty" );
        return H->Elements[0];
    }

    MaxElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];

    for(i=1; 2*i <=H-Size; i = Child) {
        Child = i*2;
*        if(Child != H->Size && H->Elements[Child+1] > H->Elements[Child])
            Child++;

*        if(LastElement < H->Elements[Child] )
            H->Elements[i] = H->Elements[Child];
        else
            break;
    } 
    H->Elements[i] = LastElement;
    return MaxElement;
}

与最小堆的删除最小元素操作相比，有2处条件判断发生改变，已用*号标出，读者可以自行体会。
（3）如果仅仅是要获得最大值，那么可以在常数时间完成O(1)。

</br>

二叉堆的应用——堆排序：

用最大堆完成堆排序，每次DeleteMax花费时间O(logN)，对N个元素进行排序就是O(NlogN)。
另外建立二叉堆花费的时间为O(N)。不解可参考->《为什么堆排序构建堆的时间复杂度是N》
所以堆排序的时间复杂度为O(NlogN)+O(N) = O(NlogN)，因为是就地排序，所以空间复杂度为O(1)。

void HeapAdjust(int *a, int i, int size) {   //调整堆
    int Child;
    int tmp;
    
    for(tmp = a[i]; 2*i+1 < size; i = Child) {
        Child = 2*i+1;   //左儿子
        if(Child != size-1 && a[Child+1] > a[Child])   //如果右儿子比左儿子大，取右儿子
            Child++;
    
        if(tmp < a[Child])
            a[i] = a[Child];
        else
          break;
    }
    a[i] = tmp;
}

void HeapSort(int *a, int size) {    //堆排序主例程
    int i;
    for(i = size/2; i>=0; i--) {    //构建堆
        HeapAdjust(a, i, size);
    }

    for(i = size-1; i>0; i--) {
        int temp = a[i];   //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面 
        a[i] = a[0];
        a[0] = temp;
        HeapAdjust(a, 0, i);  //重新调整堆顶节点成为大顶堆
    }
    
}

注：堆排序代码的堆结点从数组索引0开始