0
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ You do realize that in C and C++, the ^ operator does an exclusive-or, not raising to a power, so your 10^9 is the same as 3, right? \$\endgroup\$ – Jerry Coffin Sep 6 '17 at 13:31
  • 1
    \$\begingroup\$ Since you have a max_priority_queue already, you should just make the comparison operation a predicate template parameter and reuse the existing code instead. After all, a min heap is just a max heap with > swapped for <. \$\endgroup\$ – Frank Sep 6 '17 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.