浅谈二叉堆

前言

复习基础数据结构，供日后学习参考吧
在这里插入图片描述
~~（放一个封面）~~

二叉堆

二叉堆分为最大堆(大顶堆)和最小堆(小顶堆)，具体区别是：

大顶堆父亲节点永远大于子节点(堆顶元素是最大的)

小顶堆父亲节点永远小于子节点(堆顶元素是最小的)

那么二叉堆如何构建？

二叉堆建立

大顶堆构建：

void big_build(int x) //堆顶下标是1
{
    b_Heap[++b_Size] = x;
    int son = b_Size;
    while (son > 1)
    {
        int fa = son >> 1;
        if (b_Heap[son] <= b_Heap[fa])
            break;
        swap(b_Heap[son], b_Heap[fa]);
        son = fa;
    }
}

小顶堆构建

void small_build(int x) //堆顶下标是1
{
    s_Heap[++s_Size] = x;
    int son = s_Size;
    while (son > 1)
    {
        int fa = son >> 1;
        if (s_Heap[son] >= s_Heap[fa])
            break;
        swap(s_Heap[son], s_Heap[fa]);
        son = fa;
    }
}

汇总完整代码：

#include <bits/stdc++.h>
using namespace std;
// 大顶堆和小顶堆的建立（最小堆+最大堆）
#define maxn 100000
int s_Size, b_Size;
int s_Heap[maxn];
int b_Heap[maxn];
void small_build(int x) //堆顶下标是1
{
    s_Heap[++s_Size] = x;
    int son = s_Size;
    while (son > 1)
    {
        int fa = son >> 1;
        if (s_Heap[son] >= s_Heap[fa])
            break;
        swap(s_Heap[son], s_Heap[fa]);
        son = fa;
    }
}
void big_build(int x) //堆顶下标是1
{
    b_Heap[++b_Size] = x;
    int son = b_Size;
    while (son > 1)
    {
        int fa = son >> 1;
        if (b_Heap[son] <= b_Heap[fa])
            break;
        swap(b_Heap[son], b_Heap[fa]);
        son = fa;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int remp;
        cin >> remp;
        big_build(remp);
        small_build(remp);
    }
    for (int i = 1; i <= n; i++)
        cout << s_Heap[i] << " ";
    cout << endl;
    for (int i = 1; i <= n; i++)
        cout << b_Heap[i] << " ";
    cout << endl;
    return 0;
}