当前位置：
  1. 首页
  2. 数据结构与算法入门
  3. 正文

什么是二叉堆？

数据结构与算法入门 0 203

面试官：写一个堆排吧

我心想：堆排是什么鬼

理解堆排，首先要理解二叉堆。理解了二叉堆的“下沉”操作，基本上就可以理解堆排了。今天我们来看一看什么是堆，以及堆的一般操作

一、优先级队列

近日，一尘遇到了烦心事，于是找老师去诉苦了

image-20230213174813407

image-20230213174823752

image-20230213174835699

image-20230213174845802

image-20230213174857233

一尘列了几个要做的事

image-20230213174909178

image-20230213174918784

一尘道出了心中的苦

image-20230213174929885

慧能：你可以做优先级最高的事情，做完后删除它，然后做剩下优先级最高的事，当然，很有可能有其他事插入进来，新插入的事情如果优先级不是最高，就不做，这样你就一直做优先级最高的事了

接着慧能顺手画了一个图

image-20230213174942327

image-20230213174954512

优先级队列中每个元素都有优先级，优先级最高的最先被处理

二、优先级队列的实现

image-20230213175005673

一尘非常想知道黑盒里面是什么

image-20230213175017290

image-20230213175029925

图片

然后我把优先级存入一个无序数组里，取出的时候遍历数组一边，找出最小值，插入的时候直接插到集合末尾

image-20230213175051548

image-20230213175102190

image-20230213175113921

image-20230213175125387

一尘画了一幅图解释道

image-20230213175138420

随后，一尘又画出了插入6后的图

image-20230213175151066

image-20230213175203321

image-20230213175214074

image-20230213175228974

三、堆

image-20230213175240183

image-20230213175250593

这里我们只讨论二叉堆，把二叉堆称为堆，堆也有d-堆，左式堆等等

image-20230213175303897

慧能看一尘不是很明白，顺手画了个图

image-20230213175319445

image-20230213175331599

慧能画了一个二叉堆实例

image-20230213175344679

image-20230213175356196

注意：二叉堆中两个孩子之前的大小没有关系，可能左孩子>=右孩子，也可能右>=左

image-20230213175407766

慧能随手画了一个小根堆和一个大根堆

image-20230213175419369

本文讨论小根堆

image-20230213175430902

image-20230213175441968

image-20230213175454222

image-20230213175503921

image-20230213175516957

image-20230213175527952

image-20230213175539785

image-20230213175549596

image-20230213182041384

4、插入操作

image-20230213182054085

每个父节点的值小于等于其左右孩子的值被称为堆的有序性，另一种情况是大于等于也称之为堆的有序性

慧能随手画了一个插入操作破坏堆有序性的图

image-20230213182106562

image-20230213182118068

image-20230213182137135

image-20230213182151428

image-20230213182202277

image-20230213182212209

image-20230213182229276

image-20230213182240245

说完，慧能飞速地写出了上浮的代码

image-20230213182252811

一尘暗自惊叹老师的代码功力

五、删除操作

image-20230213182305311

一尘听完此话紧张的手心出汗，但还是硬着头皮想了想，突然灵光一现

图片

image-20230213182330068

随后一尘画出了交换后的图

image-20230213182350130

image-20230213182400097

image-20230213182412056

image-20230213182422315

image-20230213182432296

image-20230213182442552

image-20230213182540395

image-20230213182553038

image-20230213182606116

image-20230213182623622

image-20230213182638513

image-20230213182651854

image-20230213182706906

image-20230213182716738

一尘刚松了口气，谁知还要写代码，只见一尘想了想，写写擦擦好几遍最终写下了如下代码

image-20230213182731091

image-20230213182742069

如图

image-20230213182754107

image-20230213182811470

只见一尘又写了一段代码

image-20230213182826544

leftIndex = 2*parentIndex;

rightIndex = 2*parentIndex+1;

image-20230213182839133

image-20230213182851701

image-20230213182902908

image-20230213182917337

看来以后得好好学数据结构与算法了，不然连时间都管理不好，一尘心想

本图片是一个尾部占位符

发表回复

后才能评论

评论(2)


数据结构与算法入门系列教程