Выполнение функции min

Question

Добрый день, я нашел эту реализацию очереди приоритетов, и я пытаюсь получить ее минимальную версию (вместо max). Я не знаю, с чего начать. Я попытался смешать признаки функций (наивная попытка), но это не заставило меня далеко. Любая помощь в том, как его реализовать, и несколько слов, объясняющих это, очень хороши. Источник ниже: Примечания Я оставил это комментарии

#include <iostream> 
#include <vector> 
#include <assert.h> 
using namespace std; 
class PriorityQueue 
{ 
    vector<int> pq_keys; 
    void shiftRight(int low, int high); 
    void shiftLeft(int low, int high); 
    void buildHeap(); 
public: 
    PriorityQueue(){} 
    PriorityQueue(vector<int>& items) 
    { 
     pq_keys = items; 
     buildHeap(); 
    } 
    /*Insert a new item into the priority queue*/ 
    void enqueue(int item); 
    /*Get the maximum element from the priority queue*/ 
    int dequeue(); 
    /*Just for testing*/ 
    void print(); 
}; 
void PriorityQueue::enqueue(int item) 
{ 
    pq_keys.push_back(item); 
    shiftLeft(0, pq_keys.size() - 1); 
    return; 
} 
int PriorityQueue::dequeue() 
{ 
    assert(pq_keys.size() != 0); 
    int last = pq_keys.size() - 1; 
    int tmp = pq_keys[0]; 
    pq_keys[0] = pq_keys[last]; 
    pq_keys[last] = tmp; 
    pq_keys.pop_back(); 
    shiftRight(0, last-1); 
    return tmp; 
} 
void PriorityQueue::print() 
{ 
    int size = pq_keys.size(); 
    for (int i = 0; i < size; ++i) 
     cout << pq_keys[i] << " "; 
    cout << endl; 
} 
void PriorityQueue::shiftLeft(int low, int high) 
{ 
    int childIdx = high; 
    while (childIdx > low) 
    { 
     int parentIdx = (childIdx-1)/2; 
     /*if child is bigger than parent we need to swap*/ 
     if (pq_keys[childIdx] > pq_keys[parentIdx]) 
     { 
      int tmp = pq_keys[childIdx]; 
      pq_keys[childIdx] = pq_keys[parentIdx]; 
      pq_keys[parentIdx] = tmp; 
      /*Make parent index the child and shift towards left*/ 
      childIdx = parentIdx; 
     } 
     else 
     { 
      break; 
     } 
    } 
    return; 
} 
void PriorityQueue::shiftRight(int low, int high) 
{ 
    int root = low; 
    while ((root*2)+1 <= high) 
    { 
     int leftChild = (root * 2) + 1; 
     int rightChild = leftChild + 1; 
     int swapIdx = root; 
     /*Check if root is less than left child*/ 
     if (pq_keys[swapIdx] < pq_keys[leftChild]) 
     { 
      swapIdx = leftChild; 
     } 
     /*If right child exists check if it is less than current root*/ 
     if ((rightChild <= high) && (pq_keys[swapIdx] < pq_keys[rightChild])) 
     { 
      swapIdx = rightChild; 
     } 
     /*Make the biggest element of root, left and right child the root*/ 
     if (swapIdx != root) 
     { 
      int tmp = pq_keys[root]; 
      pq_keys[root] = pq_keys[swapIdx]; 
      pq_keys[swapIdx] = tmp; 
      /*Keep shifting right and ensure that swapIdx satisfies 
      heap property aka left and right child of it is smaller than 
      itself*/ 
      root = swapIdx; 
     } 
     else 
     { 
      break; 
     } 
    } 
    return; 
} 
void PriorityQueue::buildHeap() 
{ 
    /*Start with middle element. Middle element is chosen in 
    such a way that the last element of array is either its 
    left child or right child*/ 
    int size = pq_keys.size(); 
    int midIdx = (size -2)/2; 
    while (midIdx >= 0) 
    { 
     shiftRight(midIdx, size-1); 
     --midIdx; 
    } 
    return; 
} 
int main() 
{ 
//example usage 
    PriorityQueue asd; 
    asd.enqueue(2); 
    asd.enqueue(3); 
    asd.enqueue(4); 
    asd.enqueue(7); 
    asd.enqueue(5); 
    asd.print(); 
    cout<< asd.dequeue() << endl; 
    asd.print(); 
    return 0; 
} 

Answer 1

Как правило, в таких задачах, то есть алгоритмах, основанных на сравнении элементов, вы можете переопределить то, что означает (a < b). (Так, например, вещи в стандартной библиотеке работают. Вы можете определить свой собственный компаратор.)

Итак, если вы измените это значение на противоположное. Вы измените порядок заказов.

Вам необходимо идентифицировать каждое сравнение элементов и переключать его. Так что для каждого фрагмента кода, подобного этому

/*if child is bigger than parent we need to swap*/ 
    if (pq_keys[childIdx] > pq_keys[parentIdx]) 

инвертировать его значение/логика.

Простого отрицание должно сделать трюк:

/*if child is NOT bigger than parent we need to swap*/ 
    if !(pq_keys[childIdx] > pq_keys[parentIdx]) 

Вам даже не нужно понимать алгоритм. Просто обратное значение того, что такое меньший элемент.

Редактировать: Дополнительное примечание. Вы могли бы фактически реорганизовать его в какой-то bool compare(T a, T b). И используйте эту функцию, где используется сравнение. Поэтому всякий раз, когда вы хотите изменить поведение, вам просто нужно изменить одно место, и оно будет последовательным. Но это в основном, чтобы избежать работы, чтобы искать каждое такое происшествие, и глупые ошибки, и когда вы пропустите один.

Answer 2

Легче:

std::prioroty_queue<int, std::vector<int>, std::greater<int>> my_queue; 

Если это часть упражнения, то я предлагаю следующие принципы дизайна из стандартной библиотеки: разделить проблему на :

1. хранения данных (например, станд :: вектор)
2. сортировки или алгоритм "heapifying" (см std::make_heap и т.д.)
3. критерии заказа (для использования 2. выше)

Ваш класс должен дать вам некоторую свободу действий, чтобы изменить любой из них независимо друг от друга. При этом вы можете тривиально изменить порядок «меньше», чем «больше».