当前位置:首页 > 记忆回溯 > 正文内容

数据结构——堆(Heap)大根堆、小根堆

MuWinds1个月前 (01-31)记忆回溯30

转载:https://www.cnblogs.com/wangchaowei/p/8288216.html

Heap是一种数据结构具有以下的特点:

1)完全二叉树;

2)heap中存储的值是偏序;

Min-heap: 父节点的值小于或等于子节点的值;

Max-heap: 父节点的值大于或等于子节点的值;

image.png

堆的存储:

一般都用数组来表示堆,i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

image.png

堆的操作:insert

插入一个元素:新元素被加入到heap的末尾,然后更新树以恢复堆的次序。

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列,现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中。

image.png

堆的操作:Removemax

按定义,堆中每次都删除第0个数据。为了便于重建堆,实际的操作是将最后一个数据的值赋给根结点,然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最大的,如果父结点比这个最小的子结点还大说明不需要调整了,反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。

image.png

堆的操作:buildHeap 堆化数组

对于叶子节点,不用调整次序,根据满二叉树的性质,叶子节点比内部节点的个数多1.所以i=n/2 -1 ,不用从n开始。

image.png

堆排序

堆建好之后堆中第0个数据是堆中最大的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最大的数据,重复上述步骤直至堆中只有一个数据时就直接取出这个数据。


标签: 数据结构

“数据结构——堆(Heap)大根堆、小根堆” 的相关文章

php如何理解严格模式declare(strict_types=1)?

严格模式的写法:decleare(strict_type=1);严格模式的声明需要放到php文件的最顶端,否则会抛出错误:Fatal error: strict_types declaration must be the very...

PHP 程式碼風格PSR

PSR-1:基本程式寫作標準1. 總覽檔案只能使用 <?php 和 <?= 標籤檔案字元編碼只能用 UTF-8 檔首無 BOM檔案應該只宣告符號 (class、function、constant)或是造成副作用(例如產生輸出、修改 .ini 檔之類)兩者擇一不應該兩個都做Namespac...

两个物块动量定理的二级结论整理

还是那样子,死记硬背没用这就是纯纯算数的活儿,理儿都摆在这了。一个经典的模型是一个物块以速度v撞向另外一个静止的物块,符合动量守恒:思考题:两个滑块相互碰撞,仍然是理想模型,动量守恒能量守恒,推导v1/v2...

go gin框架实现限流

接手一个项目,甲方希望在项目中实现指定用户的限流,这需要我们在go项目中实现一个限流器。限流器的实现有很多经典的思想,不过令牌桶的思路简单,运行效率高,它是以恒定的速度往木桶里加入令牌,木桶满了则不再加入令牌。服务收到请求时尝试从木桶中取出一个令牌,如果能够得到令牌则继续执行后续的业务逻辑。如果没有...

AMD Ryzen Windows睡死问题解决

更新AMD芯片组驱动(不分任何笔记本厂家): https://seaou.lanzouw.com/iQL0V2m7wnuh...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。