优先队列和堆的区别

Question

看起来优先队列只是一个带有正常队列操作（例如插入、删除、取顶等）的堆。这是正确解释优先队列的方式吗？我知道可以用不同的方法构建优先队列，但如果我要从一个堆中构建优先队列，是否需要创建一个优先队列类并给出构建堆和队列操作的说明，或者不需要构建类呢？

我的意思是，如果我有一个构建堆的函数和插入、删除等操作的函数，是否需要将所有这些函数都放在一个类中，或者只需通过在 main 中调用它们来使用这些说明。

我的问题是，拥有一组函数是否等价于将它们存储在某个类中，并通过类使用它们，还是仅使用函数本身。

下面是实现优先队列的所有方法。这已足以称之为实现，还是需要将其放入指定的优先队列类中？

#ifndef MAX_PRIORITYQ_H
#define MAX_PRIORITYQ_H
#include <iostream>
#include <deque>
#include "print.h"
#include "random.h"

int parent(int i)
{
    return (i - 1) / 2;
}

int left(int i)
{
    if(i == 0)
        return 1;
    else
        return 2*i;
}

int right(int i)
{
    if(i == 0)
        return 2;
    else
        return 2*i + 1;
}

void max_heapify(std::deque<int> &A, int i, int heapsize)
{
    int largest;
    int l = left(i);
    int r = right(i);
    if(l <= heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;
    if(r <= heapsize && A[r] > A[largest])
        largest = r;
    if(largest != i) {
        exchange(A, i, largest);
        max_heapify(A, largest, heapsize);
        //int j = max_heapify(A, largest, heapsize);
        //return j;
    }
    //return i;
}

void build_max_heap(std::deque<int> &A)
{
    int heapsize = A.size() - 1;
    for(int i = (A.size() - 1) / 2; i >= 0; i--)
        max_heapify(A, i, heapsize);
}

int heap_maximum(std::deque<int> &A)
{
    return A[0];
}

int heap_extract_max(std::deque<int> &A, int heapsize)
{
    if(heapsize < 0)
        throw std::out_of_range("heap underflow");
    int max = A.front();
    //std::cout << "heapsize : " << heapsize << std::endl;
    A[0] = A[--heapsize];
    A.pop_back();
    max_heapify(A, 0, heapsize);
    //int i = max_heapify(A, 0, heapsize);
    //A.erase(A.begin() + i);
    return max;
}

void heap_increase_key(std::deque<int> &A, int i, int key)
{
    if(key < A[i])
        std::cerr << "New key is smaller than current key" << std::endl;
    else {
        A[i] = key;
        while(i > 1 && A[parent(i)] < A[i]) {
            exchange(A, i, parent(i));
            i = parent(i);
        }
    }
}

void max_heap_insert(std::deque<int> &A, int key)
{
    int heapsize =  A.size();
    A[heapsize] = std::numeric_limits<int>::min();
    heap_increase_key(A, heapsize, key);
}

- Mars

---

不，那不完全正确。你有阅读相关的维基百科文章吗？ - Konrad Rudolph

使用堆可以实现优先队列。这是一种流行且高效的方法，但并不是唯一的方法，因此您可以实现没有堆的优先队列。 - Vaughn Cato

这是两种不同的抽象类。优先队列是一种类似于队列的抽象数据类型，它保存了优先级，因此当你向队列添加元素时，它不会被添加到队列的最后，而是被添加到一个“适合”的位置上。堆通常是一个用于存储数据的内存块。 - Grzegorz

（至少）有两种“堆”。您提到的“内存池”是一种，而堆数据结构则是另一种。 - Sebastian

@Sebastian，不幸的是，这个术语被重载了。请参阅维基百科消歧义页面。堆数据结构与堆（也称为自由存储区）不同，请参阅堆数据结构和堆（编程）。 - Lorenzo Donati support Ukraine

这个问题现在在维基百科上已经得到了明确的回答：http://en.wikipedia.org/wiki/Priority_queue - Snicolas

Answer 1

优先队列是一个抽象数据类型。它是描述特定接口和行为的简写方式，但并不涉及底层实现。

堆是一种数据结构。它是一种存储数据的特定方式，使得某些操作非常高效。

恰巧地，堆是实现优先队列的很好的数据结构，因为堆数据结构能够高效地执行优先队列接口所需的操作。

- Benjamin Lindley

---

或者可以说，“堆”是一组数据结构的家族，它们共同维护“堆属性”，但是以不同的方式实现，从而具有略微不同的性能特征。 - Steve Jessop

如果在构造函数中没有明确定义，它将作为std::vector实现，并且不会涉及底层实现的任何内容。 - 4pie0

@计算机：C++标准对于std::priority_queue类模板的底层实现做出了一些承诺，但我正在讨论一般的计算机科学问题，与任何语言或库无关。 - Benjamin Lindley

这是一个很棒的答案。 - Jinhua Wang

非常感谢。 - Indiana Jones

按照同样的逻辑，我们不能说堆本身就是一个抽象数据类型，而其具体实现则是二叉树数据结构吗？ - Adham

Answer 2

拥有一个恰好符合所需接口的类（只需插入和弹出最大值）具有其优点。

• 你可以稍后更换实现（例如，使用列表而不是堆）。
• 阅读使用队列的代码的人不需要理解堆数据结构的更复杂接口。

我想知道是否拥有一组函数相当于将它们存储在某个类中并通过类使用它们或仅直接使用这些函数。

就"程序行为如何"而言，它基本上是等价的。但从"人类读者容易理解程序的程度"来看，它并不等价。

- Sebastian

Answer 3

术语“优先队列”是指用于对元素的优先级进行排序的通用数据结构。有多种方法可以实现这一点，例如各种有序树结构（例如伸展树效果较好）以及各种堆，例如d堆或斐波那契堆。从概念上讲，堆是一种树形结构，其中每个节点的权重都不小于该节点所在子树中任何节点的权重。

- Dietmar Kühl

---

只是确认一下，堆是优先队列的一种类型，这样说是否正确？ - Aditya Prakash

@AdityaPrakash 堆可以用于实现优先队列。虽然我一时想不出其他用途，但可能还有其他用途不能被视为优先队列... - Dietmar Kühl

Answer 4

C++标准模板库提供了make_heap、push_heap和pop_heap算法，用于堆（通常实现为二叉堆），可以操作任意随机访问迭代器。它将迭代器视为数组的引用，并使用数组到堆的转换。它还提供了容器适配器priority_queue，将这些功能封装在类似于容器的类中。然而，并没有标准支持减少/增加键操作。 priority_queue是指完全由可以对其执行的操作定义的抽象数据类型。在C++ STL中，prioroty_queue因此是基本容器（vector、list和deque是基本容器，因为它们不能相互构建而不会失去效率）的序列适配器之一，定义在头文件中（在我的情况下是）。从其定义中可以看出，（正如Bjarne Stroustrup所说）：

容器适配器提供了对容器的有限接口。特别地，适配器不提供迭代器；它们只能通过其专门的接口使用。

在我的实现中，prioroty_queue被描述为：

/**
   *  @brief  A standard container automatically sorting its contents.
   *
   *  @ingroup sequences
   *
   *  This is not a true container, but an @e adaptor.  It holds
   *  another container, and provides a wrapper interface to that
   *  container.  The wrapper is what enforces priority-based sorting 
   *  and %queue behavior.  Very few of the standard container/sequence
   *  interface requirements are met (e.g., iterators).
   *
   *  The second template parameter defines the type of the underlying
   *  sequence/container.  It defaults to std::vector, but it can be
   *  any type that supports @c front(), @c push_back, @c pop_back,
   *  and random-access iterators, such as std::deque or an
   *  appropriate user-defined type.
   *
   *  The third template parameter supplies the means of making
   *  priority comparisons.  It defaults to @c less<value_type> but
   *  can be anything defining a strict weak ordering.
   *
   *  Members not found in "normal" containers are @c container_type,
   *  which is a typedef for the second Sequence parameter, and @c
   *  push, @c pop, and @c top, which are standard %queue operations.
   *  @note No equality/comparison operators are provided for
   *  %priority_queue.
   *  @note Sorting of the elements takes place as they are added to,
   *  and removed from, the %priority_queue using the
   *  %priority_queue's member functions.  If you access the elements
   *  by other means, and change their data such that the sorting
   *  order would be different, the %priority_queue will not re-sort
   *  the elements for you.  (How could it know to do so?)

模板：

  template<typename _Tp, typename _Sequence = vector<_Tp>,
       typename _Compare  = less<typename _Sequence::value_type> >
    class priority_queue
    {

与此相反，堆描述了它的元素如何在内存中获取和存储。 它是一种（基于树的）数据结构，其他的如数组、哈希表、结构体、联合、集合等，除此之外还满足堆属性：所有节点都比其子节点大或小，这取决于为堆定义的比较谓词。

因此，在我的堆头文件中，我找不到堆容器，而是一组算法。

  /**
   * @defgroup heap_algorithms Heap Algorithms
   * @ingroup sorting_algorithms
   */ 

像这样:

• __is_heap_until
• __is_heap函数
• __push_heap函数
• __adjust_heap函数
• __pop_heap函数
• make_heap函数
• sort_heap函数

它们（不包括被注释为“此函数是扩展，不是C++标准的一部分”的__is_heap函数）都与堆相关。

   *  @ingroup heap_algorithms
   *
   *  This operation... (what it  does)

- 4pie0

Answer 5

优先队列是一种抽象数据结构，可以用许多方式实现-未排序数组、排序数组、堆-。它就像一个接口，为您提供了堆的签名：

class PriorityQueue {
   top() → element
   peek() → element
   insert(element, priority)
   remove(element)
   update(element, newPriority)
   size() → int
}

堆是使用数组的优先队列的具体实现（它可以在概念上表示为一种特定类型的二叉树），用于保存元素和强制执行不变量的特定算法。不变量是在数据结构的整个生命周期中始终保持真实的内部属性。

以下是优先队列实现的性能比较：

- Yilmaz

Answer 6

并不完全是这样。名称中的“优先级”源于队列中条目的优先级值，定义了它们...当然：优先级。有许多实现此类优先级队列的方法。

- JensG