配对堆的自适应属性

配对堆专为完美使用优先队列而实现。优先队列跟踪一组对象的最小值，因此每次我们从队列中取出某个元素时，它始终是最小值。使用迪杰斯特拉算法计算图中最短路径时，通常会实现优先队列。

配对堆非常完美，因为它们易于使用并且在实际应用中运行良好。具体来说，它们在摊销时间方面运作得非常好。这意味着尽管单个操作会花费更长的时间，但队列在整个生命周期中的所有操作的总和很快。配对堆更容易编码，并且通常比斐波那契堆运行得更好。

配对堆具有非常简单的属性。每个堆都与一个对象或值相关联。每个堆还配备了一组子堆。对象的总是大于（或小于）其子堆的值。

堆有一些基本操作 −

min(heap) – 获取最小值。此函数非常简单。它查找堆的顶部值。

merge(heap1, heap2) – 合并或组合两个堆。将具有最大值的堆添加到另一个堆的子堆。此函数也很快。

更新于：2020 年 1 月 2 日

113 次浏览

开启你的 职业生涯

结业即可取得认证

开始
广告