堆 Heaptype
status
date
slug
summary
tags
category
icon
password
Property
堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。
每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。STL 中的
priority_queue 其实就是一个大根堆。（小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。一些功能强大的堆（可并堆）还能（高效地）支持
merge等操作。一些功能更强大的堆还支持可持久化，也就是对任意历史版本进行查询或者操作，产生新的版本。堆的分类
操作 \ 数据结构 | 配对堆 | 二叉堆 | 左偏树 | 二项堆 | 斐波那契堆 |
插入（insert） | |||||
查询最小值（find-min） | |||||
删除最小值（delete-min） | |||||
合并 (merge) | |||||
减小一个元素的值 (decrease-key) | |||||
是否支持可持久化 | 否 | 是 | 是 | 是 | 否 |
习惯上，不加限定提到“堆”时往往都指二叉堆。
二叉堆
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。在现实中通常把堆 (一种完全二叉树) 使用顺序结构的数组来存储。
堆总是满足下列性质：
- 堆中某个结点的值总是不大于（大根堆）或不小于（小根堆）其父结点的值
- 堆总是一棵完全二叉树
如果当前节点在数组中的索引为 ，那么有：
- 其左子节点在数组中的索引为
- 其右子节点在数组中的索引为
- 其父节点在数组中的索引为
常见的二叉堆有两种形式，分别是【大根堆】和【小根堆】，其中前者的堆顶是整个序列中最大的元素，后者的堆顶则是整个序列中最小的元素。如果下标 满足，其中表示最后一个元素的下标，判断当前序列为大根堆还是小根堆：
- 大根堆：满足
arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]
- 小根堆：满足
arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]
二叉堆的操作分为入堆和出堆。入堆或者出堆后需要重新调整堆的结构，使其满足大根堆或者小根堆的条件，这个操作的过程分为【上浮】和【下沉】。
上浮
先将入堆元素添加在数组末尾位置，然后与其父节点进行比较。对于大根堆而言，如果大于父节点，则与父节点交换位置；对于小根堆而言，如果小于父节点，则与父节点交换位置，重复上述操作，直到满足大根堆/小根堆的条件：
下沉
先将堆顶元素出堆，然后将数组最末尾位置的元素放入到堆顶位置，与其左、右子节点进行比较。对于大根堆而言，找出值最大的子节点并与其交换位置；对于小根堆而言，找出值最小的子节点并与其交换位置，重复上述操作，直到其满足大根堆/小根堆的条件：
无论是上浮操作还是下沉操作，其时间复杂度均为，空间复杂度均为。