type
status
date
slug
summary
tags
category
icon
password
很多的应用场景只需要取得当前数据集中最大或者最小的元素，而对于数据集中其它数据，并不关系
Priority Queue
优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。
优先队列 是一种抽象的数据类型，而 堆 是一种数据结构。所以 堆 是实现 优先队列 的一种方式。
实现 优先队列 的方式有很多种，比如数组和链表，而 堆 能够使 优先队列 的插入、删除操作都在 的时间复杂度内完成，并且以 获得最大或者最小的元素
Heap
满足以下条件的二叉树，可以称之为 堆：
- 完全二叉树；
- 每一个节点的值都必须 大于等于或者小于等于 其孩子节点的值。
插入操作
插入到末尾，然后上浮
删除操作
与末尾元素交换位置，然后不断下沉
实现
用静态数组存完全二叉树
建立空堆，然后将元素一个个插入，时间复杂度为
但是直接将数组堆化，时间复杂度为（等差数列）
TODO：代码实现
C++
用到
<algorithm>堆排序
时间复杂度：
空间复杂度：
TopK问题
不用堆化全部元素的方法：
求前k大的元素，则维护一个大小为K的小根堆，遍历数组：
- 如果堆不满，则直接插入；
- 如果堆已满，则比较堆顶元素与当前元素，大于堆顶元素则删除堆顶元素同时将此元素插入；
直到遍历整个数组后，堆中的全部元素即为前k大的元素。
TopKth问题
上面问题最后结果的堆顶就是Kth
题目
- URL:/article/1dbcfdac-1191-4341-8964-c8b0e2b314b9
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!