大顶堆、小顶堆

堆

堆
- 堆的维护
- - 1.自我初始化
  - 代码
  - 2.插入时维护
  - 时间复杂度

代码如有误欢迎指出

本文是最近在整理排序算法的时候写到堆排序单拎出来写的，目前只有维护代码

堆

堆是一颗完全二叉树，同时保证所有双亲都比自己的孩子大（可以相等

堆的维护

使用数组存储，长度为 n+1，从 1 索引开始存储，对 $i$ ， $2 i$ 和 $2 i + 1$ 是孩子， $\frac{i}{2}$ 是双亲

1.自我初始化

把一个现有数组自我初始化为堆：
原理：
先把小的子树维护好，然后由小至大维护
从第二小的子树开始（最小的子树是叶子）
找到子树，维护就是看左右子树是否有应该当堆顶的（如小顶堆就是找是否有比双亲节点小的孩子）

实现：
索引值最大的第二小的子树是几？是 $\frac{n}{2}$ ！
注意，调整子树的堆顶之后有可能影响子树的子树，需要往下继续维护，直到叶子

维护小顶堆示例：
在这里插入图片描述

代码

/*测试样例1
8 
53 17 72 5 39 67 94 25
得到:
5 17 67 25 39 72 94 53
*/
/*测试样例2
9 
53 17 72 5 39 94 67 25 1
得到:
1 5 67 17 39 94 72 25 53
*/
#include <iostream>
using namespace std;
int nums[105];
int n;

void adjustDown(int heap[],int i,int n)
{
 
    int child_p = 2 * i;    //i结点（在循环中是指对应调整的子树）的孩子的索引
    int parent = heap[i];   //本子树的根结点的值
    while (child_p<=n)      //保证双亲是有孩子结点的，叶子结点本身就是排好的堆，不需要调整
    {
        if (child_p + 1 <= n && heap[child_p + 1] < heap[child_p])   child_p++;//选中左右孩子中更小的和双亲作比较
        if (heap[child_p] < parent)
        {
            heap[child_p / 2] = heap[child_p];//将孩子的值赋给父亲
            child_p *= 2;
        }
        else
        {
            break;
        }
    }
    heap[child_p/2] = parent;//这一步容易忘记！！！！就是赋回i结点的值！当然如果每次比较完用tmp去做交换就可以不用这么麻烦，我就是不想用tmp交换，因为那样有三次赋值，而这样写只有一次
}

int main()
{
    //数组初始化
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> nums[i];
    }

    //小顶堆初始化
    for (int i = n/2; i >=1; i--)
    {
        adjustDown(nums, i, n);
    }
    //排序后展示
    for (int i = 1; i <= n; i++)
    {
        cout << nums[i] << ' ';
    }
    cout << endl;
}

2.插入时维护

思路和自我初始化差不多，就是从下而上，从插入结点的双亲比较，往上找需要调整的每一个结点

/*测试样例1
8
53 17 72 5 39 67 94 25
得到:
5 17 67 25 39 72 94 53
*/
/*测试样例2
9
53 17 72 5 39 94 67 25 1
得到:
1 5 67 17 39 94 72 53 25(注意，这个和自我初始化的结果不一定一样)
*/
#include <iostream>
using namespace std;
int nums[105];
int n;

void heapInsertAdjust(int heap[], int i)//尾部插入后做的调整
{
    int child = heap[i];    //最初插入的值，循环中做每次比较的孩子
    int parent_p = i / 2;   //循环中每次比较的双亲索引
    int lastParent_p = i;   //循环中最后一次赋给双亲的位置，默认不交换就是i原地（其实就是“上一个双亲”的位置，因为/2会默认向下取整，需要用这个标记
    while (parent_p >= 1)
    {
        if (heap[parent_p] > child)
        {
            heap[lastParent_p] = heap[parent_p];  //将双亲的值赋给孩子，继续往上找
            lastParent_p = parent_p;              //更新赋值位置
            parent_p /= 2;
        }
        else break;
    }
    heap[lastParent_p] = child;
}

int main()
{
    //数组初始化
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int tmp;
        cin >> nums[i];
        heapInsertAdjust(nums, i);//插入的时候调整
    }


    //排序后展示
    for (int i = 1; i <= n; i++)
    {
        cout << nums[i] << ' ';
    }
    cout << endl;
}