优先级队列和堆之间的区别

Question

似乎优先级队列只是具有正常队列操作的堆,如insert,delete,top等.这是解释优先级队列的正确方法吗？我知道您可以以不同的方式构建优先级队列但是如果我要从堆构建优先级队列,则需要创建优先级队列类并提供构建堆和队列操作的说明,或者是否真的不需要构建班级？

我的意思是如果我有一个函数来构建一个堆和函数来执行像insert,delete这样的操作,我是否需要将所有这些函数放在一个类中,或者我可以通过调用它们来使用它们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);
}

Answer 1

优先级队列是抽象数据类型.它是描述特定接口和行为的简写方式,并且没有说明底层实现.

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

实际上,堆是实现优先级队列的非常好的数据结构,因为堆数据结构有效的操作是优先级队列接口所需的操作.

Answer 2

拥有一个具有所需接口的类(只需插入和弹出 - 最大？)具有它的优点.

• 您可以稍后交换实现(例如,列表而不是堆).
• 读取使用队列的代码的人不需要理解堆数据结构的更难的接口.

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

如果您只是考虑"我的程序如何表现",那么它几乎是等效的.但它并不等同于"人类读者理解我的程序有多容易"

Answer 3

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