プライオリティ キューは、挿入、削除、トップなどの通常のキュー操作を備えた単なるヒープのようです。これはプライオリティ キューを解釈する正しい方法ですか? さまざまな方法でプライオリティ キューを構築できることは知っていますが、ヒープからプライオリティ キューを構築する場合、プライオリティ キュー クラスを作成し、ヒープとキュー操作を構築するための指示を与える必要がありますか、それとも構築する必要はありませんか?クラス?
つまり、ヒープを構築する関数と、挿入や削除などの操作を行う関数がある場合、これらすべての関数をクラスに配置する必要がありますか、または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);
}