当前位置：首页 > news >正文

算法笔记-第九章-堆(未完成-=需要好好搞搞题目）

news 来源：原创 2024/5/12 18:36:55

算法笔记-第九章-堆

堆的基础知识
- 堆的相关性质
- 堆序性
- 堆的存储
- 堆的基础操作
- - 下滤操作
  - 上滤操作
- 建堆
- - 自顶向下建堆法
  - 自下而上建堆法
- 堆的应用
- - 优先队列
大佬讲解
向下调整够建大顶堆

堆的基础知识

堆的相关性质

大佬视频总结

堆必须是一个完全二叉树
完全二叉树只允许最后一行不为满，且最后一行必须是从左到右排序，之间不可以右间隔
堆的存储=节点下标为i，左子节点下标为2i+1，右子节点下标为2i+2

堆序性

在这里插入图片描述
小根堆

堆的存储

类似于层次遍历的形式进行排序
将下标对应到数组当中，这样一个堆就可以用一个数组来代表

在这里插入图片描述

堆的基础操作

下滤操作

如何将树调整成堆呢？
将破坏堆序性的元素和他的最大的子结点比较，如果小于则进行交换

在这里插入图片描述

上滤操作

现在就是只有树的最后一个元素破坏了堆序性
方法：将他和他的父元素比较，若大于父节点则进行交换，直到无法上移为止

建堆

问题：如果有一个乱序的数组如何进行建堆呢？
有两种方法：自下而上和自上而下

自顶向下建堆法

方法：

插入堆
上滤

将新元素放到堆的最后一位，然后进行上滤操作

自下而上建堆法

先把下面的元素调整成堆
然后再对父节点进行下滤操作
方法是：每次对于倒数第二排父节点进行下滤操作，直到根节点操作完毕

堆的应用

优先队列

两种操作：一个是插入队列，一个是弹出最小元素
在这里插入图片描述

一般使用小根堆来实现，弹出之后需要调整操作‘
方法：
将最后一个元素放到根节点，然后进行下滤操作

插入操作：上滤操作就是插入操作

在这里插入图片描述

大佬讲解

向下调整够建大顶堆

在这里插入图片描述

#include <cstdio>
#include <algorithm>
using namespace std;const int MAXN = 1000 + 1;
int heap[MAXN];void downAdjust(int low, int high) {int i = low, j = i * 2;while (j <= high) {if (j + 1 <= high && heap[j + 1] > heap[j]) {j = j + 1;}if (heap[j] > heap[i]) {swap(heap[j], heap[i]);i = j;j = i * 2;}else {break;}}
}void createHeap(int n) {for (int i = n / 2; i >= 1; i--) {downAdjust(i, n);}
}
int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &heap[i]);}createHeap(n);for (int i = 1; i <= n; i++) {printf("%d", heap[i]);if (i < n) {printf(" ");}}return 0;
}