堆和优先队列优先队列

什么是优先队列？优先队列(priority queue)普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高进先出（largest-in，first-out）的行为特征。

文章插图
优先队列和堆排序的区别是什么？简单来说：堆排序是一种排序算法，利用堆结构完成排序的功能；优先队列是一种数据结构，它是利用堆来实现。
具体来说，堆排序过程：建堆→堆顶就是最大(或小)值，然后堆顶跟最后一个元素交换→调整堆，反复这个过程，直到堆里面所有元素都交换好；
而优先队列：建堆→堆顶元素就是优先级最高（或最低）的元素了，可以利用优先级这个数据结构来描述某个问题，比如有一批不断输入的日期，我想要在任何时刻都能以O(1)的速度得到已经输入的日期中的最早日期，那么就可以用优先队列这个数据结构存储日期元素啦。
【数据结构】堆（优先队列）：二叉堆、d堆、左式堆、斜堆与二项队列这是数据结构类重新复习笔记的第五篇，同专题的其他文章可以移步：
堆（Heap）又称为优先队列（priority queue），在队列的基础上，堆允许所有队列中的元素不一定按照先进先出（FIFO）的规则进行，而是使得每个元素有一定的优先级，优先级高的先出队列。
优先队列至少存在两个重要的操作：
有几种简单而明显的方法实现优先队列。
二叉堆（binary heap）是一种对于优先队列的实现，可以简称为堆
堆是一棵完全二叉树（complete binary tree），即所有节点都必须有左右两个子节点，除了最后一排元素从左向右填入，直到没有元素为止。
很显然，一棵高为h的完全二叉树有 2^h 到 2^(h+1)-1 个节点，即其高度为 logN 向下取整。
完全二叉树的好处在于其规律性，可以使用一个数组而不需要链表来表示
对于数组中任一位置 i 上的元素，其左儿子在位置 2i 上，右儿子在左儿子后的单元 (2i+1) 上，它的父亲则在位置 i/2 向下取整上。
因此，不仅不需要链，而且遍历该树所需要的操作也极简单，在大部分计算机上都可能运行得非常快。唯一问题是最大的堆的大小需要事先估计。
使操作可以快速执行的性质是堆序性质（heap-order property）：对于每一个节点X，X的父节点中的键小于等于X中的键，除没有父节点根节点外。
【堆和优先队列优先队列】 将待插入的元素首先放置在最后一个位置上，以保证他是一个完全二叉树，然后将该元素与其父节点（i/2向下取整）比较，如果比其父节点小，就将两者互换，互换后再和新的父节点比较，这种方式称为上滤（percolate up），得到一个小顶堆（min heap），如果比较的时候是较大的值向上走，就会得到一个大顶堆（max heap）
比如向一个小顶堆中插入元素14的操作：
找出、返回并删除最小元非常简单，最小元就是根节点处的元素，将其返回并删除。接下来是处理这个B 。首先拿下最后一个元素X，如果元素X比B的两个子节点都小，可以直接将X插入到B的位置，如果X比B的两个子节点中的任意一个大，就不能插入，此时找到两个子节点中较小的那个放到B处，B转而移至这个子结点处。重复如上的步骤直到X可以插入B处为止。这个操作成为下滤（percolate down）
比如从一个小顶堆中删除根节点
decreaseKey(p, A)操作减小在位置p处的元素的值，减少量为A，可以理解为调高了某个元素的优先级。操作破坏了堆的性质，从而需要上滤操作进行堆的调整。
increaseKey(p, A)操作增加在位置p处的元素的值，增加量为A，可以理解为降低了某个元素的优先级。操作破坏了堆的性质，从而需要下滤操作进行堆的调整。
remove(p)操作删除在堆中位置p处的节点，这种操作可以通过连续执行decreaseKey(p, ∞)和deleteMin()完成，可以理解马上删除某个一般优先级的元素
即将一个原始集合构建成二叉堆，这个构造过程即进行N次连续的 insert 操作完成
定理：包含 2^(h+1)-1 个节点且高度为h的理想二叉树（perfect binary tree）的节点的高度和为 2^(h+1)-1-(h+1)
d堆（d-Heaps）是二叉堆的简单推广，它与二叉堆很像，但是每个节点都有d个子节点，所以二叉堆是d为2的d堆。d堆是完全d叉树。比如下边的一个3堆。
d堆比二叉堆浅很多，其insert的运行时间改进到 O(logdN)。但是deleteMin操作比较费时，因为要在d个子节点中找到最小的一个，需要进行d-1次比较。d堆无法进行find操作，而且将两个堆合二为一是很困难的事情，这个附加操作为merge合并。

堆和优先队列 优先队列

秒懂生活扩展阅读

堆和优先队列优先队列