当前位置: 首页 > article >正文

数据结构与算法学习笔记----堆

数据结构与算法学习笔记----堆

@@ author: 明月清了个风

@@ last edited: 2024.12.2

ps⛹从这里开始调整了文章结构,先讲解算法和数据结构基本原理,再给出例题,针对例题中的应用再讲解思路。

堆是一种完全二叉树,常用于实现优先队列(priority_queue)等功能,可以根据堆内元素关系分为大根堆小根堆

  • 大根堆:每个父节点的值都大于或等于其子节点的值,根节点是堆中最大的元素。
  • 小根堆:每个父节点的正都小于或等于其子节点的值,根节点是对重最小的元素。

对于堆来说(以小根堆为例),常用的操作有建堆、取出最小元素、删除最小元素、删除某个元素、修改某个元素

  1. 建堆O(n)

    堆化(heapify)是堆数据结构中的一个核心操作。建堆的过程其实也是一个排序的过程,以小根堆为例,在读入所有的元素之后进行堆化,使用到的操作是下沉(down),步骤如下:

    • 假设当前节点是最大值
    • 然后比较左子节点和右子节点,找到三个节点中最小的一个。
    • 如果当前节点不是最小值,就与最小值节点交换,并递归下沉被交换的元素,这个数所在的新的子树中仍可能不满足堆的条件。

    这里给出的示例代码使用的是数组的存储方式(当然也可以用链表进行存储)

    从下标1开始存储,左子节点是2 * i,右子节点是2 * i + 1

    每次对于一个节点,在其作为根节点存在的子树中找到最小的节点(也就是在i, 2 * i, 2 *i + 1中的最小值)放到这颗子树的根节点上,最后递归被交换的点。

    ⭐️这里有个注意点:建堆的循环中从cnt / 2开始(如果是从0开始存的,就是从cnt / 2 - 1开始)。

    解释:在完全二叉树中,叶子节点的索引cnt / 2 + 1cnt,从cnt / 2 + 1开始的所有节点都是叶子节点,那么对于叶子节点而言,他们自身满足堆的性质,在以他们自己为根节点的子树中是最小值(因为他们也没有子节点和他们对比了),因此不需要调整他们的位置。对于非叶子节点而言,需要进行对比确保其子树堆的性质,因此可以从cnt / 2开始遍历。

    int h[N], cnt;
    
    void down(int u)
    {
        int t = u;
        if(u * 2 <= cnt && h[u* 2] < h[u]) t = u * 2;
        if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[u]) t = u * 2 + 1;
        if(u != t)
        {
            swap(h[u], h[t]);
            down(t);
        }
    }
    
    int main()
    {
        
        for(int i = 1; i <= cnt; i ++) cin >> h[i];
        
        for(int i = cnt / 2; i ; i --) down(i);
        
    }
    
  2. 取最小值 O(1)

    取堆中的最小值很简单,返回第一个元素h[1]即可

  3. 删除最小值 O( l o g ( n ) log(n) log(n))

    对于数组存储的二叉树,删除最小值也很简单,只需要用树的最后一个元素将其覆盖h[1] = h[cnt --],再进行一次排序down(1),在最坏情况下, 这个树会沿着树的高度一路down到最底层,因此时间复杂度为O( l o g ( n ) log(n) log(n))。

  4. 删除某个元素

    对于删除某个元素而言,这里考虑的同样是删除最小值的操作,若要删除编号为k的元素,则用树的最后一个元素将其覆盖h[k] = h[cnt --]后,再进行一次堆化排序操作down(k),时间复杂度也和上述操作相同。

  5. 修改某个元素

    修改元素一般只需要将这个值改掉h[k] = x,; cnt ++再堆化一遍donw(k)就行。

Acwing 836. 合并集合

[原题链接](838. 堆排序 - AcWing题库)

输入一个长度为 n n n的整数数列,从小到大输出前 m m m小的数。

输入格式

第一行输入整数 n n n m m m

第二行包含 n n n个整数,表示整数数列。

输出格式

共一行,包含 m m m个整数,表示整数数列中前 m m m小的数。

数据范围

1 ≤ n , m ≤ 1 0 5 1 \leq n, m \leq 10^{5} 1n,m105,

1 ≤ 数列中元素 ≤ 1 0 9 1 \leq 数列中元素 \leq 10^9 1数列中元素109

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

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

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

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

Acwing 836. 合并集合

[原题链接](839. 模拟堆 - AcWing题库)

维护一个集合,初始时集合为空,支持如下几种操作:

  1. I x,插入一个数x;
  2. PM,输出当前集合中的最小值;
  3. DM,删除当前集合中的最小值(数据保证此时的最小值唯一);
  4. D k,删除第k个插入的数。
  5. C k x,修改第k个插入的数,将其变为x;

现在要进行N次操作,对于所有第 2 2 2个操作,输出当前集合的最小值。

输入格式

第一行输入整数 N N N

接下来 N N N行,每行包含一个操作指令。

输出格式

对于每个输出指令PM,输出一个结果,表示当前集合中的最小值。

数据范围

1 ≤ N ≤ 1 0 5 1 \leq N \leq 10^{5} 1N105,

− 1 0 9 ≤ x ≤ 1 0 9 -10^9 \leq x \leq 10^9 109x109

思路

这道题中的操作都是上面讲过的基本操作,需要注意的地方是位置的映射,因为指定要删除的元素编号是按插入的顺序计算的。我们建堆完成后,数组内元素的顺序就不同了,因此需要保存这个数据,如果是用结构体存储的话相对会更简单,这里给个示例,具体实现就不写了(如果后面有碰或者大家有需要再补吧),需要修改第 k k k个元素就遍历一遍堆找到insertOrderk的元素即可。

typedef struct HeapNode {
    int value;                  // 节点的值
    int insertionOrder;         // 插入顺序,表示该节点是第几次插入堆中的
    struct HeapNode* left;      // 指向左子节点的指针
    struct HeapNode* right;     // 指向右子节点的指针
    struct HeapNode* parent;    // 指向父节点的指针
} HeapNode;

由于使用的是数组存储元素,因此额外的信息(也就是插入顺序)需要另外开数组进行存储,并且因为会涉及到堆中两个元素值的互换,那么插入顺序的索引也需要进行互换,因此开两个数组ph[N]hp[N]

前者ph[k]的含义是第 k k k个插入的元素在堆中的索引,也就是要找到第 k k k个插入元素在堆中排序后的位置操作是k = ph[k]

后者hp[k]的含义是堆中索引为k的元素是第几个插入的。

这里比较绕,画个图解释一下
在这里插入图片描述

图中右侧为一个堆,节点中的数字表示其在堆中排序后的位置(即数组h),现有两个节点ab需要交换位置。

假设a是第一个插入的元素,b是第三个插入的元素,那么对于节点a来说ph[1] = 4,hp[4] = 1,对于节点b来说ph[3] = 2, hp[2] = 3

那么交换时,不仅要交换值,还要交换索引,因此交换操作的代码为

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

解释:对于要交换的节点ab,首先交换其插入的索引swap(ph[hp[a]], ph[hp[b]])hp[a]hp[b]分别是两节点在堆中的索引,然后交换两者在树中位置的索引swap(hp[a], hp[b]),最后交换两者的值swap(h[a], h[b])

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;
int h[N], ph[N], hp[N], cnt;

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 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= cnt && 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 / 2] > h[u])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

int main()
{
    cin >> n;
    
    while(n --)
    {
        char op[5];
        int k, x;
        cin >> op;
        if(!strcmp(op, "I"))
        {
            cin >> x;
            cnt ++;
            m ++;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if(!strcmp(op, "PM")) cout << h[1] << endl;
        else if(!strcmp(op, "DM"))
        {
            heap_swap(1, cnt);
            cnt --;
            down(1);
        }
        else if(!strcmp(op, "D"))
        {
            cin >> k;
            k = ph[k];
            heap_swap(k, cnt);
            cnt --;
            up(k);
            down(k);
        }
        else
        {
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }
    
    return 0;
    
   
}

http://www.kler.cn/a/419516.html

相关文章:

  • day32|leetcode 509.斐波那契数,70.爬楼梯,746.使用最小花费爬楼梯
  • 什么是隐式类型转换?隐式类型转换可能带来哪些问题? 显式类型转换(如强制类型转换)有哪些风险?
  • 人工智能技术在外骨骼机器人中的应用,发展历程与原理介绍
  • 普及组集训--图论最短路径
  • 婚礼照片分享平台WeddingShare
  • Java NIO 全面详解:初学者入门指南
  • C 语言学习的经典书籍有哪些?
  • 【数据分析】伊藤公式
  • 【golang】单元测试,以及出现undefined时的解决方案
  • Linux离线安装docker(arm64架构cpu)极速版
  • Python面试实战:高效处理海量日志,找出高频IP
  • 怎么修改虚拟机上Ubuntu的ip为静态ip
  • SpringBoot源码解析(六):打印Banner
  • Brain.js(五):不同的神经网络类型和对比,构建神经网络时该如何选型?
  • 用 Python 从零开始创建神经网络(十三):训练数据集(Training Dataset)
  • ArcGIS对地区进行筛选提取及投影转换
  • Elasticsearch 的存储与查询
  • 数据科学家创建识别假图像的工具
  • 【Go 基础】channel
  • Qt窗口的闪烁QWebEngineView