直入主题！

1.堆

（二叉）堆是数组，可看成近似的完全二叉树。例如A[1..n]中，A[i]的父节点是A[i/2],左右孩子分别为A[2i],A[2i+1]（假设都存在）。
于是可得父节点，左孩子，右孩子的下标：

Parent(i)
    return i / 2

Left(i)
    return 2 * i

Right(i)
    return 2 * i + 1

二叉堆的两种形式： 最大堆与最小堆。
最大堆：除了根以外的节点i都满足：
A[Parent(i)] >= A[i]
最小堆：除了根以外的节点i都满足：
A[Parent(i)] <= A[i]

2.维护堆的性质

运用Max-Heapify函数，对于每个节点i，找出它与它的左右孩子中最大的并交换。伪代码如下：

Max-Heapify(A, i) // 修改判断大小即可变为维护最小堆性质
    l = Left(i)  // 左孩子下标
    r = Right(i) // 右孩子下标
    if l <= A.heap-size and A[l] > A[i]
        largest = l
    else
        largest = i
    if r <= A.heap-size and A[r] > A[largest]
        largest = r
    if largest != i
        exchange A[i] with A[largest]
        Max-Heapify(A, largest) // 防止交换后largest节点不满足

可以证明在数组只有根节点的一个子节点不满足堆的性质时，运用该函数能让数组变为最大（小）堆。

3.构建堆

首先引入一个性质：堆的叶的下标为n/2+1,n/2+2,...n。
根据这个性质可得：堆非叶下标为1,2,...n/2。
即前n/2个节点都有子节点。
因此在构建堆时，从n/2开始向上堆建。

Build-Max-Heap(A)
    A.heap-size = A.length
    for i=A.length/2 downto 2
        Max-Heapify(A, i)

对于每一个节点i，都满足子数组的根节点至多有一个子节点不满足堆的性质，因此用Max-Heapify函数能使得该子数组成为堆。

4.堆排序

最大堆中最大的节点一定为A[1],根据这一特性来对数组排序。

Heapsort(A)
    Build-Max-Heap(A) // 构建最大堆
    for i=A.length downto 2
        exchange A[i] with A[1]
        A.heap-size = A.heap-size - 1
        Max-Heapify(A, 1)

构建最大堆后，A[1]为最大值，将其与最后一项调换，并缩减堆的大小，前i-1项满足根节点的一个子节点不满足堆的性质，用Max-Heapify函数让其成为堆，依次循环即可对A排序。
（PS：用栈可实现从大到小排序）

5.优先队列

使用堆能使优先队列的一些操作变得简单。
找出队列最大关键字：

Heap-Maximum(A)
    return A[1]

找出并删除队列最大关键字：

Heap-Extract-Max(A)
    if A.heapsize < 1
        error"heap underflow"
    max = A[1]
    A[1] = A[A.heap-size]
    A.heap-size = A.heap-size - 1
    Max-Heapify(A, 1)
    return max

去掉最大值的方法为让A[1]变为A[A.heap-size]，然后缩减堆大小并建堆。
将元素i的关键字增加到key：

Heap-Increase-Key(A, i, key)
    if A[i] > key
        error
    A[i] = key
    while i > 1 and A[i] > A[Parent(i)]
        exchange A[i] with A[Parent(i)]
        i = Parent(i)

插入元素：

Max-Heap-Insert(A, key)
    A.heap-size = A.heap-size + 1
    A.[A.heap-size] = -∞
    Heap-Inscrease-Key(A, A.heap-size, key)

警告！！！以下为C++代码！！！！

堆排序：

#include<iostream>
using namespace std;
int a[100005] = {0}, n, size;
int parent(int i) //叫爸爸 
{
    return i / 2;
}
int left(int i) //左儿子 
{
    return i * 2;
}
int right(int i) //右儿子 
{
    return i * 2 + 1;
}
void Max_Heapify(int a[], int i) //让爸爸最大 
{
    int l = left(i);
    int r = right(i);
    int largest = 0;
    if(l <= size && a[l] > a[i])
        largest = l;
    else
        largest = i;
    if(r <= size && a[r] > a[largest])
        largest = r;
    if(largest != i)
    {
        swap(a[i], a[largest]);
        Max_Heapify(a, largest);
    }
}
void Build_Max_Heap(int a[]) //使数组成为最大堆 
{
    for(int i = n / 2; i >= 1; i--)
        Max_Heapify(a, i);
}
void Heapsort(int a[]) //堆排序，最大堆的根节点为堆的最大值 
{
    Build_Max_Heap(a);
    for(int i = n; i >= 2; i--)
    {
        swap(a[1], a[i]);
        size--;
        Max_Heapify(a, 1);
    }
}
int main()
{
    cin>>n;
    size = n;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    Heapsort(a);
    for(int i = 1; i <= n; i++)
        cout<<a[i]<<" ";
    return 0;
}

优先队列：
#include<iostream>
#include<cmath>
using namespace std;
int a[100005] = {0}, n, size;
int parent(int i) //叫爸爸 
{
    return i / 2;
}
int left(int i) //左儿子 
{
    return i * 2;
}
int right(int i) //右儿子 
{
    return i * 2 + 1;
}
void Max_Heapify(int a[], int i) //让爸爸最大 
{
    int l = left(i);
    int r = right(i);
    int largest = 0;
    if(l <= size && a[l] > a[i])
        largest = l;
    else
        largest = i;
    if(r <= size && a[r] > a[largest])
        largest = r;
    if(largest != i)
    {
        swap(a[i], a[largest]);
        Max_Heapify(a, largest);
    }
}
void Build_Max_Heap(int a[]) //使数组成为最大堆 
{
    for(int i = n / 2; i >= 1; i--)
        Max_Heapify(a, i);
}
void Heapsort(int a[]) //堆排序，最大堆的根节点为堆的最大值 
{
    Build_Max_Heap(a);
    for(int i = n; i >= 2; i--)
    {
        swap(a[1], a[i]);
        size--;
        Max_Heapify(a, 1);
    }
}
int Heap_Maximum(int a[]) //返回堆最大值 
{
    return a[1];
}
int Heap_Extract_Max(int a[]) //返回堆最大值并删除
{
    int max = a[1];
    a[1] = a[size];
    size--;
    Max_Heapify(a, 1);
    return max;
}
void Heap_Increase_Key(int a[], int i, int key) //让a[i]增加到key
{
    if(a[i] > key)
        cout<<"error"<<endl;
    else
    {
        a[i] = key;
        while(i > 1 && a[i] > a[parent(i)])
        {
            swap(a[i], a[parent(i)]);
            i = parent(i);
        }
    }
}
int main()
{
    cout<<"输入数组大小："; 
    cin>>n;
    size = n;
    cout<<"输入数组元素：";
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    Build_Max_Heap(a);
    for(int j = 1, i = 1; i <= n; i++)
    {
        cout<<a[i]<<" ";
        if(i == pow(2, j)-1)
        {
            cout<<endl;
            j++;
        }
    }
    cout<<endl<<"输入改变元素及值:";
    int x, y;
    cin>>x>>y;
    size = n;
    Heap_Increase_Key(a, x, y);
    for(int j = 1, i = 1; i <= n; i++)
    {
        cout<<a[i]<<" ";
        if(i == pow(2, j)-1)
        {
            cout<<endl;
            j++;
        }
    }
    cout<<endl<<"Max:"<<Heap_Maximum(a)<<endl;
    int maxi = Heap_Extract_Max(a);
    cout<<"Max:"<<maxi<<", Size:"<<size;
    return 0;
}