After getting suggestions for Maximum Priority Queue I have written program for Minimum Priority Queue. Help me improve this code.
#include <iostream>
#include <vector>
template<typename T>
class min_priority_queue
{
size_t parent(size_t index)
{
return (index-1)/2;
}
void min_heapify(std::vector<T>& array, size_t index)
{
size_t smallest;
size_t left = (2*index) + 1;
size_t right = left + 1;
if(left < array.size() && array[left] < array[index])
smallest = left;
else
smallest = index;
if(right < array.size() && array[right] < array[smallest])
smallest = right;
if(smallest != index)
{
std::swap(array[index], array[smallest]);
min_heapify(array, smallest);
}
}
public:
min_priority_queue() {}
min_priority_queue(const min_priority_queue<T>& mpq) = delete;
min_priority_queue& operator=(min_priority_queue const&) = delete;
void build_min_heap(std::vector<T>& array)
{
for(int64_t i = (int64_t(array.size())/2) - 1; i >= 0; i--)
min_heapify(array, i);
}
T heap_minimum(std::vector<T>& array)
{
return array[0];
}
T heap_extract_min(std::vector<T>& array)
{
T min = array[0];
array[0] = array[array.size() - 1];
array.resize(array.size() - 1);
min_heapify(array, 0);
return min;
}
void heap_decrease_key(std::vector<T>& array, size_t index, T value)
{
if(value > array[index])
{
std::cerr << "New value is larger than the current value\n";
return;
}
else
{
array[index] = value;
while(index > 0 && array[parent(index)] > array[index])
{
std::swap(array[index], array[parent(index)]);
index = parent(index);
}
}
}
void min_heap_insert(std::vector<T>& array, T value)
{
array.resize(array.size() + 1);
array[array.size() - 1] = 10^9;
heap_decrease_key(array, array.size() - 1, value);
}
void print_heap(const std::vector<T>& array)
{
for(size_t i = 0; i < array.size(); i++)
std::cout << array[i] << " ";
}
};
int main()
{
std::vector<int> v;
min_priority_queue<int> mpq1;
v.push_back(1);
v.push_back(8);
v.push_back(6);
v.push_back(3);
v.push_back(7);
mpq1.build_min_heap(v);
std::cout << "Queue: ";
mpq1.print_heap(v);
std::cout<< '\n';
std::cout << "Extract-Minimum: " << mpq1.heap_extract_min(v) << '\n';
std::cout << "New Queue: ";
mpq1.print_heap(v);
mpq1.min_heap_insert(v, 2);
std::cout << "\nNew Queue after inserting 2: ";
mpq1.print_heap(v);
std::cout << '\n';
}
I am unable to build queue for char
or string
because in
void min_heap_insert(std::vector<T>& array, T value)
{
array.resize(array.size() + 1);
array[array.size() - 1] = 10^9;
heap_decrease_key(array, array.size() - 1, value);
}
I have written array[array.size() - 1] = 10^9;
How to fix this so that I can build queue for char
and string
values.
^
operator does an exclusive-or, not raising to a power, so your10^9
is the same as3
, right? \$\endgroup\$