C++ 优先队列和堆的区别

Difference between priority queue and a heap

提问by Mars

It seems that a priority queue is just a heap with normal queue operations like insert, delete, top, etc. Is this the correct way to interpret a priority queue? I know you can build priority queues in different ways but if I were to build a priority queue from a heap is it necessary to create a priority queue class and give instructions for building a heap and the queue operations or is it not really necessary to build the class?

优先级队列似乎只是一个带有插入、删除、顶部等普通队列操作的堆。这是解释优先级队列的正确方法吗？我知道你可以用不同的方式构建优先级队列，但是如果我要从堆构建优先级队列，是否有必要创建一个优先级队列类并给出构建堆和队列操作的说明，还是没有必要构建班上？

What I mean is if I have a function to build a heap and functions to do operations like insert, delete, do I need to put all these functions in a class or can I just use the instructions by calling them in main.

我的意思是，如果我有一个函数来构建堆和执行插入、删除等操作的函数，我是否需要将所有这些函数放在一个类中，或者我可以通过在main.

I guess my question is whether having a collection of functions is equivalent to storing them in some class and using them through a class or just using the functions themselves.

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

What I have below is all the methods for a priority queue implementation. Is this sufficient to call it an implementation or do I need to put it in a designated priority queue class?

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

#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);
}

采纳答案by Sebastian

Having a class with exactly the interface you need (just insert and pop-max?) has its advantages.

拥有一个完全符合您需要的接口的类（只是插入和弹出最大？）有其优势。

• You can exchange the implementation (list instead of heap, for example) later.
• Someone reading the code that usesthe queue doesn't need to understand the more difficult interface of the heap data structure.

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

I guess my question is whether having a collection of functions is equivalent to storing them in some class and using them through a class or just using the functions themselves.

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

It's mostly equivalent if you just think in terms of "how does my program behave". But it's not equivalent in terms of "how easy is my program to understand by a human reader"

如果您只考虑“我的程序的行为方式”，这几乎是等效的。但这并不等同于“我的程序有多容易被人类读者理解”

回答by Benjamin Lindley

A priority queue is an abstract datatype. It is a shorthand way of describing a particular interface and behavior, and says nothing about the underlying implementation.

优先级队列是一种抽象数据类型。它是描述特定接口和行为的速记方式，并没有说明底层实现。

A heap is a data structure. It is a name for a particular way of storing data that makes certain operations very efficient.

堆是一种数据结构。它是一种特殊的数据存储方式的名称，它使某些操作非常有效。

It just so happens that a heap is a very good data structure to implement a priority queue, because the operations which are made efficient by the heap data strucure are the operations that the priority queue interface needs.

恰巧堆是实现优先级队列的一个很好的数据结构，因为堆数据结构使高效的操作是优先级队列接口需要的操作。

回答by 4pie0

The C++ Standard Template Library provides the make_heap, push_heap and pop_heap algorithms for heaps (usually implemented as binary heaps), which operate on arbitrary random access iterators. It treats the iterators as a reference to an array, and uses the array-to-heap conversion. It also provides the container adaptor priority_queue, which wraps these facilities in a container-like class. However, there is no standard support for the decrease/increase-key operation.

C++ 标准模板库为堆（通常实现为二进制堆）提供了 make_heap、push_heap 和 pop_heap 算法，这些算法在任意随机访问迭代器上运行。它将迭代器视为对数组的引用，并使用数组到堆的转换。它还提供了容器适配器priority_queue，它将这些设施包装在一个类似容器的类中。但是，没有对减少/增加键操作的标准支持。

priority_queue referes to abstract data typedefined entirely by the operations that may be performed on it. In C++ STL prioroty_queueis thus one of the sequence adapters- adaptors of basic containers (vector, list and deque are basic because they cannot be built from each other without loss of efficiency), defined in <queue>header (<bits/stl_queue.h>in my case actually). As can be seen from its definition, (as Bjarne Stroustrup says):

priority_queue 是指完全由可能对其执行的操作定义的抽象数据类型。因此，在 C++ 中，STLprioroty_queue是序列适配器之一——基本容器的适配器（向量、列表和双端队列是基本的，因为它们不能在不损失效率的情况下相互构建），在<queue>头文件<bits/stl_queue.h>中定义（实际上是在我的情况下）。从它的定义可以看出，（如 Bjarne Stroustrup 所说）：

container adapter provides a restricted interface to a container. In particular, adapters do not provide iterators; they are intended to be used only through their specialized interfaces.

容器适配器为容器提供受限接口。特别是，适配器不提供迭代器；它们旨在仅通过其专用接口使用。

On my implementation prioroty_queueis described as

在我的实现中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:

模板：

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

In opposite to this, heapdescribes how its elements are being fetched and stored in memory. It is a (tree based) data structure, others are i.e array, hash table, struct, union, set..., that in addition satisfies heap property: all nodes are either [greater than or equal to] or [less than or equal to] each of its children, according to a comparison predicate defined for the heap.

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

So in my heap header I find no heap container, but rather a set of algorithms

所以在我的堆头中我没有找到堆容器，而是一组算法

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

like:

喜欢：

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

• __is_heap_until
• __is_heap
• __push_heap
• __adjust_heap
• __pop_heap
• make_heap
• 排序堆

all of them (excluding __is_heap, commented as "This function is an extension, not part of the C++ standard") described as

所有这些（不包括 __is_heap，评论为“这个函数是一个扩展，不是 C++ 标准的一部分”）描述为

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

回答by Dietmar Kühl

The term priority queuerefers to the general data structure useful to order priorities of its element. There are multiple ways to achieve that, e.g., various ordered tree structures (e.g., a splay tree works reasonably well) as well as various heaps, e.g., d-heaps or Fibonacci heaps. Conceptually, a heapis a tree structure where the weight of every node is not less than the weight of any node in the subtree routed at that node.

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

回答by JensG

Not really. The "priority" in the name stems from a priority value for the entries in the queue, defining their ... of course: priority. There are many ways to implement such a PQ, however.

并不真地。名称中的“优先级”源于队列中条目的优先级值，定义了它们……当然是：优先级。然而，有很多方法可以实现这样的 PQ。