5.20

前言吐槽：

今天是5.20啦，但是作为单身修狗的我只能和代码过啦。。。继续加油算法打卡！！！

堆排序：

堆就是一棵完全二叉树
二叉堆是一种支持插入，删除，查询最值的数据结构。他其实是一棵满足"堆性质"的完全二叉树，树上的每个节点带有一个权值。若树中的任意一个节点的权值都小于等于其父节点的权值，则称该二叉树满足"大根堆性质”。若树中任意一个节点的权值都大于等于其父节点的权值，则称该二叉树满足"小根堆性质”。
这里采用一个数组来保存二叉堆。逐层从左到右为树中的节点依次编号，把此编号作为节点在数组中存储的位置（下标）。在这种存储方式中，父节点编号等于子节点编号除以2，左子节点编号等于父节点编号乘2，右子节点编号等于左子节点编号乘2加1；
两个基本操作：

down(int u);简而言之就是一颗树从u的位置开始往当前这棵树下面的，如果下面有比u位置的小的话，就去交换

void down(int u) {

   // 这个模板的作用是父节点和其两个孩子节点的最小值，再交换父节点和这个最小值

   int t = u;

   if (u * 2 <= cnt && h[u * 2] < h[t])

       t = 2 * u;

   if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t])

       t = 2 * u + 1;

   if (u != t) {

       swap(h[u], h[t]);

       down(t);

       //每次这个t都是最小的哈

       // 递归处理这个输入的值，直到它down到不能down为止，即整棵树又变成了一个小根堆.

   }

}

down(int u);简而言之就是一颗树从u的位置开始往当前这棵树下面的，如果下面有比u位置的小的话，就去交换

 void up(int u) {

       while (u / 2 && h[u / 2] > h[u]) {

           swap(h[u], h[u / 2]);

           u /= 2;

       }

   }

题目链接：https://www.acwing.com/problem/content/description/840/

#include "iostream"

using namespace std;

const int N = 100010;

int h[N], cnt;

void down(int u) {

    int t = u;

    if (u * 2 <= cnt && h[u * 2] < h[t])

        t = 2 * u;

    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t])

        t = 2 * u + 1

    if (u != t) {

        swap(h[u], h[t]);

        down(t);

    }

}

void up(int u) {

    while (u / 2 && h[u / 2] > h[u]) {

        swap(h[u], h[u / 2]);

        u /= 2;

    }

}

int main() {

    int n, m;

    cin >> n >> m;

    for (int i = 1; i <= n; i++)

        cin >> h[i];

    cnt = n;

    /*

       cnt来存节点的最大下标,因为找左右孩子需要用2*u和2*u+1，

       为了防止边界值问题，需要判断2*u < n,2*u+1<n;

       并且，cnt也可以看成指向堆尾的一个指针。

   */

    for (int i = n / 2; i; i--)

        down(i);

    //初始化小根堆

    // 用down函数将整棵树调整为一个小根堆

    // 从2分之n开始down，建堆，时间复杂度为O(n)

    while (m--) {

        cout << h[1] << " ";

        h[1] = h[cnt--];

        down(1);

    }

}

巴特西

磊磊零基础打卡算法：day17 c++堆排序

5.20

最新文章

热门文章