堆排列~~手写堆



简单来说堆就是维护一个数据集合,堆的实质是一个二叉树;

堆的性质:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
附上图 嘿嘿~:
堆排列~~手写堆
今天我们说的小顶堆的
堆排列
介个问题(我才不会告诉你们我只学了小顶堆~小声bb)~~

储存问题

(这里说一下,因为我们这次是手写堆的教程,跟STL中堆有所不同,4、5操作在STL中是无法完成的,,,还有就是储存问题
STL中堆是使用优先队列进行存储;
手写堆是使用一个一维数组进行存储;(嗯,对的 ,一个一维数组;)

(一般为了方便会把根节点记为1而不是0)
在数组中储存的位置一般就是,第一个为根节点,接下来是根节点的左儿子,,,
(简单来说就是我们第X位置存放根节点的话
它的左儿子为 第2X个位置;
右儿子 第2X+1个位置;

主要操作

主要就是两个操作down(x)还有up(x)
所谓 down(x);
就是从上到下进行处理;

举个栗子~~
堆排列~~手写堆
若将 1处位置—>4改为10
堆排列~~手写堆
此时与堆的性质不符,将1处与其左右儿子相比较,找出最小值,交换两处位置,(因为堆顶为最小值)
堆排列~~手写堆
同理与2处与其左右儿子相比较,,最总结果为:
堆排列~~手写堆
同理up(x)操作为从下到上搜索
例如
堆排列~~手写堆
5处 9改为—>2;
与down不同,up只与其父节点比较,,,
2<8 将3处5处交换
继续向上搜索 2<4 交换 1处3处
结束;

// h[N]存储堆中的值, h[1]是堆顶,x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点,及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

好,接下来我们康康主要问题

主要问题

主要包括以下5个问题
1.插入一个数X;
插入一个数从末尾插入:

h[++size]=x;

2.求集合中的最小值
最小值就是根节点

h[1]

3.删除最小值
删除事就是用最末尾元素覆盖第一个然后down

h[1]=h[size];
size--;
down(1);

4.删除任意一个元素(删除第x个)
删除也是用末尾元素覆盖这个元素,,但这个元素需要判断,,这里有个简单的办法就是down 与up都操作一次,,,主意在运行的时候只会选择其一

h[x]=h[size];
size--;
down(x);
up(x);

5.修改任意一个元素(第x个改为xx)
与第四个差不多;

h[x]=xx;
down(x);
up(x);

就介个样子吧
贴个题;
堆排序https://www.acwing.com/problem/content/840/
AC代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+6;

int h[N];
int n,m;
int siz;

void down(int u)
{
    int t=u;
    if(u*2<=siz&&h[t]>h[u*2])t=u*2;
    if(u*2+1<=siz&&h[t]>h[u*2+1])t=u*2+1;
    if(u!=t)
    {
        swap(h[t],h[u]);
        down(t);
    }
}

int main()
{
   // int m;int size;
    cin>>n>>m;
    siz=n;
    for(int i = 1; i <= n; i ++)
    cin>>h[i];
    for(int i=n/2;i>0;i--)
    down(i);
    while(m--)
    {
        cout<<h[1]<<' ';
        h[1]=h[siz];
        siz--;
        down(1);
    }
    return 0;
}

第一次写多多包涵大家都不容易
哦了,拜拜~~

堆排列~~手写堆堆排列~~手写堆 kuaichongya 发布了1 篇原创文章 · 获赞 1 · 访问量 15 私信 关注
上一篇:python 继承


下一篇:struct和typedef struct区别