这里涉及到了堆结构,作为引入,要先讲讲一种特殊的树结构——完全二叉树

完全二叉树

完全二叉树就是像下图一样的二叉树,所有叶结点的深度相同,并且所有内部结点都有两个子结点

看这个图就很好理解什么叫完全二叉树了。真的很完美啊哈哈哈。

但是,有另外一种树结构也叫做完全二叉树。准确来说就是近似是完全二叉树。

长这样子:

上面这种二叉树,叶节点的深度的最大差距是1,最下层叶节点都集中分布在这层最左边的若干位置上,那么这种二叉树我们也可以把它叫做完全二叉树。

二叉堆

上面这种类型的数据结构我们将它称为二叉堆。二叉堆在逻辑上虽然是完全二叉树,但是它却是以1为起点的一维数组表示的。假设表示二叉堆的数组为A,二叉堆的大小(元素的数量)为H,那么二叉堆的元素就存储在 A[1, … , H] 中,其中根的下标是1.观察可以发现,只要一个结点的下标i确定了,那么它的父节点就是floor(i/2),左子结点下标是2*i, 右子结点的下标是2*i+1。

二叉堆和完全二叉树的区别之一在于,二叉堆中存储的各结点的键值需要保证堆具有以下性质之一

·最大堆性质: 结点的键值都小于等于其父结点的键值。

·最小堆性质: 结点的键值都大于等于其父结点的键值。

满足最大堆性质的二叉堆叫做最大堆,满足最小堆性质的二叉堆叫做最小堆。

最大堆的根结点中存储着最大的元素,最小堆的根结点中存储着最小的元素。

需要注意的是,二叉堆中只有父子结点之间有大小关系的限制,而兄弟结点之间并没有大小关系的限制。

应用二叉堆这种数据结构,我们就可以在保持数据大小关系的前提下,有效地取出优先级最高的元素,或者添加新的元素。

构建完全二叉树

下面要实现一个程序,读取以完全二叉树形式表示的二叉堆。注意,这里只是构建一棵完全二叉树,并不需要这个树满足二叉堆的规则。

输入两行数据,第一行是元素的个数

第二行是各个结点的值。

要求按结点id顺次输出结点的父结点、左子结点、右子结点的值。如果这些结点不存在,那么就不用输出。

题目出自

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_A

题目编号是 ALDS1_9_A

样例输入

5
7 8 1 2 3

样例输出

node 1: key = 7, left key = 8, right key = 1, 
node 2: key = 8, parent key = 7, left key = 2, right key = 3, 
node 3: key = 1, parent key = 7, 
node 4: key = 2, parent key = 8, 
node 5: key = 3, parent key = 8, 

这道题我们只需要根据完全二叉树的定义,就能生成这棵完全二叉树。

完全二叉树的代码实现

#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;


int main()
{
    long long nd[260];
    int h;
    cin>>h;
    for(int i=1;i<=h;i++)
    {
        cin>>nd[i];
    }

    for(int i=1;i<=h;i++)
    {
        printf("node %d: key = %lld, ",i, nd[i]);
        if(floor(i/2)!=0)
            printf("parent key = %lld, ", nd[int(floor(i/2))]);
        if(2*i<=h)
            printf("left key = %lld, ", nd[2*i]);
        if(2*i+1<=h)
            printf("right key = %lld, ", nd[2*i+1]);

        cout<<endl;

    }
}

最大堆

有了上面生成完全二叉树的基础,我们就能根据最大堆的性质来生成最大堆。

最大堆的生成有一个叫做堆化的过程,在这个过程中,利用自己写的一个max_Heapify函数,使得 A[i] 的值一致向叶结点方向移动,直至它找到合适的位置。这个过程能通过递归来实现。

但是如果从完全二叉树的根入手来解决这个问题的话,就会发现整个操作变得异常的复杂。

所以,我们可以从叶结点来入手解决这个问题。

首先,我们会发现叶结点由于没有子结点,根本不需要向下进行任何的对换操作。那么我们就直接研究叶结点的父结点就好了。

由于完全二叉树每一层的结点数量最大是上一层的两倍,所以,我们只需要从结点id为H/2的结点开始,终点是结点id=1的结点,都进行一遍max_Heapify就可以生成最大堆了。

每次执行max_Heapify的时候,当前结点i的左右子树都已经是最大堆了,所以,我们只需要关注当前结点该移动到哪个位置而已。

生成最大堆的代码实现

题目来源:

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_B

在这个程序中,输入数据的格式和上一题一样

我们要实现把一棵完全二叉树变成一个最大堆。那就按照上面的思路,从叶结点入手,自下而上的处理

#include<iostream>
using namespace std;

long long nd[500009];
int h;

void max_Heapify(int i)
{
    int l = 2*i;
    int r = 2*i+1;

    //从左子结点、自身、右子结点中选出值最大的结点

    int largest = i;
    if(l<=h&&nd[l]>nd[largest])
        largest = l;
    if(r<=h&&nd[r]>nd[largest])
        largest = r;

    if(largest!=i)
    {
        swap(nd[i], nd[largest]);
        max_Heapify(largest);
    }

}

int main()
{
    cin>>h;
    for(int i=1;i<=h;i++)
    {
        cin>>nd[i];
    }

    for(int i=h/2;i>=1;i--)
        max_Heapify(i);

    for(int i=1;i<=h;i++)
        cout<<" "<<nd[i];
    cout<<endl;
}

生成最小堆

我们只需要把上面的生成最大堆的代码稍加修改,就能改成生成最小堆的代码。

只要把max_Heapify函数改成下面的min_Heapify函数就可以了。其实就是改变了交换元素的规则。


void min_Heapify(int i)
{
    int l = 2*i;
    int r = 2*i+1;

    //从左子结点、自身、右子结点中选出值最小的结点

    int smallest = i;
    if(l<=h&&nd[l]<nd[smallest])
        smallest = l;
    if(r<=h&&nd[r]<nd[smallest])
        smallest = r;

    if(smallest!=i)
    {
        swap(nd[i], nd[smallest]);
        min_Heapify(smallest);
    }

}

你也可能喜欢

发表评论