堆的定义

(二叉)堆是一个数组，可以被看成一个近似的完全二叉树，树上的每一个结点对应数组中的一个元素，如图

假若A[i]为堆的一个结点，则他的左右子节点为A[2*i], A[2*i+1],根结点为A[1]。即A[1]的子结点为A[2]和A[3]

堆可以分为最大堆和最小堆

最大堆：最大堆中某个结点的值必须小于等于其父结点的值，即A[parent(i)] >= A[i]

最小堆：最小堆中某个结点的值必须大于等于其父结点的值，即A[parent(i)] <= A[i]

堆的维护

如图(a)中，违背了最大堆的性质，4 < 14 ,但4却是14的父亲，所以需要维护堆，经过(b),使得变成 (c) 这种情况,满足最大堆中某个结点的值必须小于等于其父结点的值

维护堆的代码执行过程：时间复杂度为O(logn)

//该函数作用为了将i点及相邻的子结点中最大的点放到i点，以此来维护最大堆的性质
void MaxHeapify(int *A, int i, int n) //A数组存放堆值，i点要进行的堆维护，n结点的总数量，n为全局变量
{
    int l = i << 1; //i结点的左结点
    int r = i << 1 | 1 ; //i结点的右结点
    if (l <= n && A[i] < A[l]) { //左孩子的值比i点的值大
        largest = l; 
    }
    else {
        largest = i;
    }
    if (r <= n && A[largest] < A[r]) {
        largest = r; //右孩子的值比i点的值大
    }
    if (largest != i) {
        swap(A[largest], A[i]); //交换值
        MaxHeapify(int *A, int largest); //继续向以largest为结点的堆维护最大堆的性质
    }
}

建堆

建堆是将一个无序数组构造成一个最大堆(最小堆反之)，是最大堆，而非有序堆

建堆代码：时间复杂度为O(n)

void BuildMaxHeap(int *A) //A数组存放堆值，n结点的总数量，n为全局变量
{
    for(int i = n/2; i>=1; i--){ 
        MaxHeapify(A, i); //进行堆维护
    }
}

建堆过程如图：

堆排序

堆排序：将堆中没有排序的点与A[1]交换，在进行对维护，使得A[1]又是在没有排序的堆中最大，循环该操作，直到A[1]点最小为止

堆排序代码：

void HeapSort(int *A) //n结点的总数量，n为全局变量
{
    BuildMaxHeap(A, n); //建堆
    for(int i = n; i >= 2; i--){
        swap(A[i],A[1]); //交换A[i]和A[1]的值
        MaxHeapify(A, 1,n-1); //堆维护
    }
}

堆排序过程：黑色表示已经排完序的

(a)中16先和1对换，1再进行堆维护，变成(b)，循环往复，得到(j)，得到有序数组(k)


堆的应用-优先队列

优先队列的实现原理是堆

优先队列分最大优先队列和最小优先队列

我们以最大优先队列为例，并且支持以下操作，下列操作代码都是底层代码

返回队列中最大值:

int HeapMaxValue(int *A)
{
    return A[1];
}

返回队列中最大值，并且将该值从队列中删去:

int HeapExtractMaxValue(int *A) //n是全局变量，代表结点个数
{
    if(n < 1) {
        printf("heap underflow!");
    }
    int max = A[1];
    A[1] = A[n];
    n--;
    MaxHeapify(A, 1); //堆维护
    return max;
}

改变某个叶子结点的值:

void HeapChangeKey(int *A, int i, int key)
{
    A[i] = key;
    while( i > 1 && A[i>>1] < A[i]) { //为了维护堆的性质
        swap(A[i>>1], A[i]); //交换
        i = i >> 1;
    }
}

改变某个结点的值，图过程:将4变成15，在与父亲结点进行比较，进行堆维护

插入值:

void HeapInsert(int *A, int key) //n是全局变量，代表结点个数
{
    n++;
    A[n] = key;
    HeapChangeKey(int *A, int n, int key);
}