---
title: "模拟堆"
created: 2025-11-28
tags:
  - 算法
---

# 模拟堆

堆就是一个完全二叉树

![[image-89eb14f2.png]]

对于小根堆来说 一个结点的孩子都比自身大（大根堆就是孩子都小于当前结点）

可以看出一种关系

对于结点1来说（n=1） 左孩子为2(2n) 右孩子为3(2n+1)

对于结点2来说 (n=2) 左孩子为4(2n) 右孩子为5(2n+1)

所以完全可以使用数组下标的n，2n，2n+1的关系去模拟这样的结构

当然 是从下标1开始使用才有意义（从0开始的话 2n还是0 没意义）

就有两种方式

如果无需管当前数是第几个数 就直接在数组中存放值（数不作对应 就简单值排序）

如果需要知道当前数是第几个数 就需要类似于模拟链表那样 用一个数组存值 另一个数组维护他们之间的物理关系（数与插入在数组时的位置仍一一对应
主要是找第k位置用）

![[image-7e973f4d.png]]

对于堆来说 一般就是进行五个操作

（1）插入一个数

（2）求集合中该点最小值

（3）删除最小值

（4）删除任意一个元素

（5）修改任意一个元素

两个实现

down(){……}

up(){……}

核心就是在于堆的调整 使其永远保持最值在上的特性

不论是操作还是构建 都是一个调整的过程

看看调整的思路（小根堆）

## **down:**

![[image-4079fdcb.png]]

这个1号位置的9 比2、3（2n,2n+1）位置的值都要大 所以要想办法沉下去

那么 就从是三个点里找到一个最小值 把他们位置交换一下

![[image-81796567.png]]

然后9换到了3号位置 与2n的6号位置去比（2n+1位置不存在） 还是更大 所以还要换

![[image-4a4728db.png]]

当交换到不能交换的时候 整颗树就又满足小根堆的性质了

```cpp
void down(int u){
  int t = u;//记录最值
  if (2 * u <= Size && h[t] > h[2 * u])
  	t = 2 * u;
  if (2 * u + 1 <= Size && h[t] > h[2 * u + 1])
  	t = 2 * u + 1;
  if (u != t){
    swap(h[u], h[t]);
    down(t);
  }
}
```

## **up:**

up就简单很多 只需要与父节点去比 如果更小就与父节点换一下（还是小根堆为例）

![[image-dcf278ea.png]]

5号位置的4不符合小根堆性质 需要调整

5/2=2的位置的点 也就是6去比 4<6 交换位置

（很巧妙的就是 不论是左孩子还是右孩子 都可以使用/2的方式找到父结点 ）

![[image-dcf278ea.png]]

再继续往上调整

2/2=1 去与1中的5比 4<5 交换位置

![[image-a023a602.png]]

这样一来 就满足了小根堆的性质

```cpp
void up(int u){
  if(u/2>0&&h[u]<h[u/2])
  {
    swap(h[u],h[u/2]);
    up(u>>1);
  }
}
```

## 五种操作

对于那五种操作其实就是变相的使用down、up进行调整

### 插入一个数

就在堆的最后一个位置（数组的可用位置处）加上一个x

![[image-d7033699.png]]

heap[++size]=x;

然后不断对它进行调整

up(size);

即可

### 求集合当中的最小值

其实就是堆形成后的堆顶元素

heap[1];

### 删除第一个元素

考虑两个问题 删除后 堆可能就发生了变化可能性质就没满足 需要调整

其二 用的是数组存储 删除元素当然还是删末尾的容易 这样无需挪动元素

所以 把最后一个元素 替换掉第一个元素 然后size-- 把最后一个元素删掉 再不断对这个n挪上来的元素进行down调整

heap[1]=heap[size];

size--;

down(1);

### 删除任意一个元素

同理

把最后一个元素挪过来 但是这里情况有点不一样 它可能往上调整也可能往下调整

不像前面一定是向下调整 所以可能还需要判断一下是进行up还是down

实际可以不用 因为down up内部都是有判断的 所以完全可以直接调用两个 它自己会选择一个进去

heap[k]=heap[size];

size--;

down[k];up[k];//只会执行一个

### 修改任意一个元素

heap[k]=x;

down[k];

up[k];

---
⬅️ [[排序矩阵查找|排序矩阵查找]] 🏠 [[00-刷题理模型]] ➡️ [[丑数|丑数]]