目录

堆的定义：

堆的基本操作的代码实现：

详情请参见《算法笔记》P335，此处只做简单的学习笔记记录。

 

堆的定义：

堆是一棵完全二叉树，树中的每个结点的值都不小于（或不大于）其左右孩子结点。

堆一般用于优先队列的实现（目前不是很懂），故默认使用的是大顶堆（每个结点的值都大于或等于其左右孩子结点，小于等于时即为小顶堆）。

 

堆的基本操作的代码实现：

堆的定义：因为堆是完全二叉树，所以可以用数组存。数组的下标为1～n，表示第1～n个结点。

const int maxn=100;
int heap[maxn],n=10;//heap为堆，n为元素个数

向下调整：O（logn）

void downAdjust(int low,int high)//low为欲调整结点的数组下标，high一般为堆的最后一个元素的数组下标
{
    int i=low,j=i*2;//i为根结点，j为左孩子结点
    while(j<=high)//存在孩子结点
    {
        if(j+1<=high && heap[j+1]>heap[j])//存在右孩子且右孩子的值大于左孩子的值
            j=j+1;//左右孩子中较大的那个的下标
        if(heap[j]>heap[i])
        {
            swap(heap[j],heap[i]);
            i=j;
            j=i*2;
        }
        else break;
    }
}

建堆：O（n）

void createHeap()//倒序遍历父亲结点
{
    for(int i=n/2;i>=1;i--)
        downAdjust(i,n);//对父亲结点向下调整
}

删除堆顶元素：O（logn）

void deleteTop()
{
    heap[1]=heap[n--];//堆顶元素和最后一个元素交换，且元素个数-1，再对当前的堆顶结点向下调整
    downAdjust(1,n);
}

向上调整：O（logn）

void upAdjust(int low,int high)//low一般为1，high一般为预调整结点的数组下标
{
    int i=high,j=high/2;//i为孩子结点，j为根结点
    while(j>=low)//根结点在[low，high]范围内
    {
        if(heap[i]>heap[j])//孩子结点的值大于根结点的值
        {
            swap(heap[i],heap[j]);
            i=j;
            j=i/2;
        }
        else break;
    }
}

添加元素：在堆尾

void insert(int x)
{
    heap[++n]=x;
    upAdjust(1,n);//向上调整新加入的结点n
}

堆排序：

void heapSort()
{
    createHeap();//建堆
    for(int i=n;i>1;i--)//直到堆里只有一个元素时
        downAdjust(1,i-1);//调整栈顶，heap[i]此时不算入堆中
}