手写堆

End_donkey 2019/9/7 21:05:18

堆定义堆是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。性质堆中某个节点的值总是不大于或不小于其父节点的值;堆总是一棵完全二叉树。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐

1.定义

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

2.性质

1.堆中某个节点的值总是不大于或不小于其父节点的值;

2.堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆是非线性数据结构,相当于一维数组,有两个直接后继。

3.应用思路(手写堆)

以最小堆为例

先把数组中的数储存起来

很显然最小的数就在堆顶,假设存储这个堆的数组叫做h的话,最小数就是h[1]。接下来,我们将堆顶的数删除,并将新增加的数23放到堆顶。显然加了新数后已经不符合最小堆的特性,我们需要将新增加的数调整到合适的位置。那如何调整呢?

我们可以将它和它的两个儿子进行比较,将儿子小的置为堆顶即可,然后依次下调

那如果是要新添加一个数,又如何操作呢?

同前面的,我们可以将新的点加到堆尾,然后上调与它的父节点比较即可。

代码

堆的操作(以大根堆为例)

关于小根堆的操作放在了文章后面。

1.堆的元素下调

void shiftdownmax(int x){
    int t,flag=0;
    while(x*2<=addmax&&flag==0){
        if(maxn[x]<maxn[x*2])t=x*2;
        else t=x;
        if(x*2+1<=addmax){
            if(maxn[t]<maxn[x*2+1])t=x*2+1;
        }
        if(t!=x){
            swap(maxn[t],maxn[x]);
            x=t;
        }else flag=1;
    }
}

2.堆的元素上调

void shiftdownmax(int x){
    int t,flag=0;
    while(x*2<=addmax&&flag==0){
        if(maxn[x]<maxn[x*2])t=x*2;
        else t=x;
        if(x*2+1<=addmax){
            if(maxn[t]<maxn[x*2+1])t=x*2+1;
        }
        if(t!=x){
            swap(maxn[t],maxn[x]);
            x=t;
        }else flag=1;
    }
}

3.建堆

由于堆的性质,只要调整一半的元素即可。

for(int i=1;i<=n;++i){
    addmax++;
    maxn[addmax]=a[i];
}
for(int i=addmax/2;i>=1;--i){
    shiftdownmax(i);
}

4.取出元素

取出第一个元素将最后一个元素放在第一个元素的位置,并且元素个数减1,对堆顶进行下调操作。

int y=maxn[1];
maxn[1]=maxn[addmax--];
shiftdownmax(1);

5.加入元素

在堆尾加入新元素并且对其进行上调操作

maxn[++addmax]=x;
shiftupmax(addmax);

4.例题

合并果子

题意

在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。

例如有3种果子,数目依次为1,2,9。可以先将1、2堆合并,新堆数目为3,耗费体力为3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

思路阐述

堆的入门题,我们只要建立一个最小堆,然后依次取出堆顶2次,将其合并之后再放入堆中即可。

代码实现

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int n,a[100005],add,p,q,sum,ans=0; 
void shiftdown(int x){
    int t,flag=0;
    while(x*2<=add && flag==0){
        if(a[x]>a[x*2])t=x*2;
        else t=x;
        if(x*2+1<=add){
            if(a[t]>a[x*2+1])t=x*2+1;
        }
        if(t!=x){
            swap(a[t],a[x]);
            x=t;
        }else flag=1;
         
    }
}
int main(){
    scanf("%d",&n);
    add=n;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=n/2;i>=1;i--){
        shiftdown(i);
    }
    for(int i=1;i<=n-1;++i){
        p=a[1];
        a[1]=a[add];
        add--;
        shiftdown(1);
        q=a[1];
        sum=q+p;
        a[1]=sum;
        shiftdown(1);
        ans=ans+sum;
    }
    printf("%d",ans);
    return 0;
}

5.习题

[TJOI2010]中位数

洛谷P1792 [国家集训队]种树

NOIP 2016 蚯蚓

6.关于堆的一些操作

1.小根堆向下调整

void shiftdownmin(int x){
    int t,flag=0;
    while(x*2<=addmin&&flag==0){
        if(minn[x]>minn[x*2])t=x*2;
        else t=x;
        if(x*2+1<=addmin){
            if(minn[t]>minn[x*2+1])t=x*2+1;
        }
        if(t!=x){
            swap(minn[t],minn[x]);
            x=t;
        }else flag=1;
    }
}

2.小根堆向上调整

void shiftupmin(int x) {
    int flag=0; 
    if(x==1) return; 
    while(x!=1 && flag==0){
        if(minn[x]<minn[x/2]) swap(minn[x],minn[x/2]);
        else flag=1;
        x=x/2;
    }
}

3.大根堆向下调整

void shiftdownmax(int x){
    int t,flag=0;
    while(x*2<=addmax&&flag==0){
        if(maxn[x]<maxn[x*2])t=x*2;
        else t=x;
        if(x*2+1<=addmax){
            if(maxn[t]<maxn[x*2+1])t=x*2+1;
        }
        if(t!=x){
            swap(maxn[t],maxn[x]);
            x=t;
        }else flag=1;
    }
}

4.大根堆向上调整

void shiftupmax(int x) {
    int flag=0; 
    if(x==1) return; 
    while(x!=1&&flag==0){
        if(maxn[x]>maxn[x/2]) swap(maxn[x],maxn[x/2]);
        else flag=1;
        x=x/2;
    }
}
随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[手写堆]http://www.zyiz.net/tech/detail-90587.html

上一篇:十分钟弄懂:数据结构与算法之美 - 时间和空间复杂度

下一篇:ES6

赞(0)

共有 条评论 网友评论

验证码: 看不清楚?
    关注微信小程序
    程序员编程王-随时随地学编程

    扫描二维码或查找【程序员编程王】

    可以随时随地学编程啦!

    技术文章导航 更多>
    扫一扫关注最新编程教程