堆（数据结构）_堆数据结构_蒸蒸，的博客-程序员秘密
1.堆的概念
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<=K2i+2 ，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。完全二叉树（除了最后一层以外上面的节点但是非空的，最后一层节点是从左到右依次排布的）。如图：
2.堆的性质
1.堆中某个节点的值总是不大于或不小于其父节点的值;
2.堆总是一棵完全二叉树。
2.堆的存储
堆的存储不同于链表的存储，堆的存储是用一个一维数组来存储的。以小根堆为例，根节点为最小值，小于它的左儿子和右儿子。根节点x存储在小标为1的数组里，左儿子存储在下标为2x的数组，右儿子存储在下标为2x+1的数组里。
3.堆的基本操作（小根堆为例）
堆的两个基本操作为down操作和up操作，顾名思义，down操作就是向下调整，up操作就是向上调整，这两个操作即可以完成以上的五个问题。
down操作如图所示移动，因为我将根节点或者某一点改变后，这一点比它的儿子点大了，所以我们要将这个点向下移动，直到重新成为一个堆。
up操作，和down操作相反，up操作是将一个点的值变小，然后不断向上移动直到成为一个新的堆。同样如图：
4.如何手写一个堆（小根堆）
1）插入一个数：插入一个数是在数组的最后面插入,然后不断往上移，heap[++size]=x，up(size)；
2）求集合中的最小值：数组第一个数一定是最小的；heap[1];
3）删除最小值: 删除最小值需要一定技巧，因为堆是一个一维数组，删除第一个比较困难，所以将数组的最后一个覆盖到第一个数，然后将最后一个数删除，最后在down操作一遍；heap[1]=heap[size],size--,down(1);
4）删除任何一个元素: 和删除根节点是类似的，假如是第k的点那么就是让最后一个数等于第k个数，这里需要判断一下看看改变后的k是变大了还是变小了，我们也可以不进行判断直接down操作一遍up操作一遍，因为无外乎只有3种情况变大，变小或者不变，所以down和up只会选择一个。heap[k]=heap[size],size--,down(k),up(k);
5）修改任何一个元素: 修改一个元素和删除一个元素同理，我们修改完以后down操作一遍up操作一遍就可以了。heap[k]=x,down(k),up(k);
5.堆的模板
down模板：
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int h[N],siz;
int n,m;
void down(int x)
{
int t=x;
if(2*x<=siz && h[2*x]<h[t]) t=2*x;
if(2*x+1<=siz && h[2*x+1]<h[t]) t=2*x+1;
if(x!=t)
{
swap(h[x],h[t]);
down(t);
}
}
up模板：
void up(int x)
{
while(x/2 &&h[x]<h[x/2])
{
headswap(x/2,x);
x/=2;
}
6.数据结构中堆和栈的不同
堆和栈在数据结构中是两种不同的数据结构。 两者都是数据项按序排列的数据结构。
栈：像是装数据的桶或者箱子
栈是大家比较熟悉的一种数据结构，它是一种具有后进先出的数据结构，也就是说后存放的先取，先存放的后取，这就类似于我们要在取放在箱子底部的东西（放进去比较早的物体），我们首先要移开压在它上面的物体（放入比较晚的物体）。
堆：像是一颗倒立的大树
堆是一种经过排序的树形数据结构，每个节点都有一个值。通常我们所说的堆的数据结构是指二叉树。堆的特点是根节点的值最小（或最大），且根节点的两个树也是一个堆。由于堆的这个特性，常用来实现优先队列，堆的存取是随意的，这就如同我们在图书馆的书架上取书，虽然书的摆放是有顺序的，但是我们想取任意一本时不必像栈一样，先取出前面所有的书，书架这种机制不同于箱子，我们可以直接取出我们想要的书。
智能推荐
linux sudo 命令详解_高兴就好2048的博客-程序员秘密
“Sudo”是Unix/Linux平台上的一个非常有用的工具，它允许系统管理员分配给普通用户一些合理的“权利”，让他们执行一些只有超级用户或其他 特许用户才能完成的任务，比如：运行一些像mount，halt，su之类的命令，或者编辑一些系统配置文件，像/etc/mtab，/etc /samba/smb.conf等。这样以来，就不仅减少了root用户的登陆次数和管理时间，也提高了系统安全性。
ORCAD17.2原理图DRC规则检查_erc matrix_ltqshs的博客-程序员秘密
ORCAD17.2原理图规则检查工具栏1.打开菜单栏2.打开工具窗口3.电气规则4.物理规则5.ERC Matrix6.DRC Reports工具栏1.打开菜单栏2.打开工具窗口3.电气规则4.物理规则5.ERC Matrix6.DRC Reports一、打开菜单栏1.根据下图1中箭头指示，选中整个.dsn文件，这样才能检查整个原理图。2.点击Tools菜单栏，选中Design...
recyclerview的刷新_文件管理器recycleview 刷新_BravestSnail的博客-程序员秘密
notifyDataSetChanged()调用此方法后，仅刷新屏幕以内的item，当下次滑动让屏幕外item进来，则再执行onBindViewHolder()进行刷新notifyItemChanged(int position)仅更新指定的position的itemnotifyItemRangeChanged()position数据发生了改变，那调用这个方法，就会回调对应position的onBindViewHolder()方法了，因为ViewHolder是复用的，所以如果position在当
DLL之__declspec(dllexport)与__declspec(dllimport)用法_赛马丸子的博客-程序员秘密
DLL之__declspec(dllexport)与__declspec(dllimport)用法
IOS 公司开发者账号申请详细教程-13810208661_挠挠大王的博客-程序员秘密
谈到苹果开发者账号，我们需要区分一下个人账号、公司账号和企业账号这三种，还有一种是教育账号，这个就不多说了。 个人账号：个人申请用于开发苹果app所使用的账号，仅限于个人使用，申请比较容易，$99。 公司账号：以公司的名义申请的开发者账号，用于公司内部的开发者共用，申请流程相对比较麻烦一下，$99。 企业账号：一般是公司规模在500人以上的企业，用于内部测试发布的账号
基于DragonBoard 410c的智能门铃系列一之系统总构架_ad3600的博客-程序员秘密
一.前言博主最近又(为什么是“又”)听闻朋友失窃，小偷直接撬了门锁入室偷窃！而很不幸，那段时间正好断电，主人家的监控摄像头因为断电无法工作！人世间最悲哀的事情莫过于“你来了，又走了，我 确 不 知 道 你 是 谁 ！！？？”好吧，原谅有类似经历的博主透露出来的悲愤之情~~于是，最近专注于智能家居开发的博主，开始对这块的安防问题重视起来。博主对着大门和监控摄像头观察了半天，突然灵
随便推点
黑马程序员——java第七天：面向对象（继承、子父类之变量、final、抽象、模板方法、接口）_构造带参子类的时候，调用哪个父类_哈哈咕嘎的博客-程序员秘密
------- android培训、java培训、期待与您交流！ ---------- 继承（extends）继承的作用：1、提高代码的复用性。2、让类与类之间产生关系，才有了多态特性。注意：（1） 千万不要为了获取其他类的功能简化代码而继承，必须是类与类之间有所属关系才可以继承。所属关系（is a）。（2） 两个类有共性没有所属关系，可以先建立一个
将DataTable一行放入另一个DataTable中_阿蒙Amon的博客-程序员秘密
概述从一个DataTable中取一行放到另一个DataTable里报错： 该行已经属于另一个表。第一种方法：DataTable dt = new DataTable();dt = ds.Tables["All"].Clone();//克隆All的结构传递给dtDataRow[] dr=this.dataSet31.Tables["Product"].Select("bc=1"); //通过条件得
vue 3.0 vue.config.js文件常用配置详解_vue3.0端口配置_丿刘先森的博客-程序员秘密
在Vue 3.0中，与2.0版本相比有一定的差别，最明显的就是缺少了build、config文件夹，而在3.0中，关于项目的配置修改，需要手动创建一个新的文件：vue.config.js。一些项目的基本配置及webpack配置可以在vue.config.js文件中完成。所以这里记录一下，3.0版本中常用的配置项：// vue.config.jsconst path = require...
无人机飞控三大算法：捷联式惯性导航系统、卡尔曼滤波算法、飞行控制PID算法_xiaoxaiohua的博客-程序员秘密
无人机飞控三大算法：捷联式惯性导航系统、卡尔曼滤波算法、飞行控制PID算法。一、捷联式惯性导航系统说到导航，不得不说GPS，他是接受卫星发送的信号计算出自身位置的，但是当GPS设备上方被遮挡后，GPS设备无法定位了。比如在室内、隧道内、地下等场所，基本收不到GPS信号。语录：任何一款有缺点的产品，必然成就了另一款能克服其缺点的产品。另一种导航方式是不依赖外界信息的，这种导航叫做惯性导航。那什么是惯性导航呢？他就是利用载体上的加速度计、陀螺仪这两种惯性远见，去分别测出飞行器的角运动信息和线运动信息，
阿里腾讯百度等大厂2020秋招面试总结，内附答案_软件测试资料侠~的博客-程序员秘密
前言我相信大多 Java 开发的程序员或多或少经历过阿里的面试，也清楚阿里 Java面试是有一定难度的，作者经历过多次阿里的面试，有满意的也有备受打击的。因此呢作者想把自己这么多次面试经历来个汇总，正值金九银十之际，希望对大家有所帮助。另外本人整理收藏了20年多家公司面试知识点整理 ，以及各种Java核心知识点免费分享给大家，我认为对面试来说是非常有用的，有需要的朋友可以可以点击这里！暗号博客园自行领取阿里面试题由于时间关系答案我就不写了（主要是懒），都总结成笔记了在阿里面试还是很舒服的，面试
模拟手机通讯录 C++编写 可改MFC_ilikekara的博客-程序员秘密
主要源程序：源码+可运行exe，30r打包出+个人微信 c1062409495源码+可运行exe，30r打包出+个人微信 c1062409495源码+可运行exe，30r打包出+个人微信 c1062409495 2.1 模拟手机通信录管理系统：2.1.1 设计思路、算法描述及实验步骤 定义类 addresslist; 定义变量：姓名，电话，家庭电话，办公电话，...