优先级队列和堆之间的区别 [英] Difference between priority queue and a heap
问题描述
似乎优先级队列只是具有正常队列操作（如插入，删除，顶部等）的堆。这是解释优先级队列的正确方法吗？我知道您可以以不同的方式构建优先级队列，但是如果我要从堆构建优先级队列，是否有必要创建优先级队列类并给出构建堆和队列操作的说明，还是不是真的有必要构建该类是什么？
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?
我的意思是，如果我有一个构建堆的函数以及执行插入，删除等操作的函数，是否需要将所有这些函数放入一个类，或者我可以通过在 main 中调用它们来使用这些指令。
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.
我想我的问题是函数的集合等效于将它们存储在某个类中，并通过一个类使用它们，或仅使用函数本身。
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);
}
推荐答案
具有与您需要的接口（只是insert和pop-max？）具有它的优点。
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 uses the 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"
这篇关于优先级队列和堆之间的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
