4
\$\begingroup\$

I have written this program for Maximim Priority Queue after studying from Introduction to Algorithm . I want to improve my code. Is there any other method to implement Priority Queue instead of Heap?

#include <iostream>
#include <vector>
#include <algorithm>

template<typename T>
void max_heapify(std::vector<T>& array, size_t index)
{
  size_t largest;
  size_t left  = (2*index) + 1;
  size_t right = left + 1;

  if(left < array.size() && array[left] > array[index])
    largest = left;
  else
    largest = index;

  if(right < array.size() && array[right] > array[largest])
    largest = right;

  if(largest != index)
  {
    int tmp = array[index];
    array[index] = array[largest];
    array[largest] = tmp;
    max_heapify(array, largest);
  }
}

template<typename T>
void build_max_heap(std::vector<T>& array)
{
  for(int64_t i = (int64_t(array.size())/2) - 1; i >= 0; i--)
  max_heapify(array, i);
}

template<typename T>
T heap_maximum(std::vector<T>& array)
{
  return array[0];
}

template<typename T>
T heap_extract_max(std::vector<T>& array)
{
  if(array.size() < 0)
  {
    std::cerr << "Heap Underflow \n";
    return -1;
  }
  else
  {
    T max = array[0];
    array[0] = array[array.size() - 1];
    array.erase(std::remove(array.begin(), array.end(), array[0]),
                  array.end());
    array.shrink_to_fit();
    max_heapify(array, 0);
    return max;
  }
}

template<typename T>
void heap_increase_key(std::vector<T>& array, size_t index, T value)
{
  if(value < array[index])
  {
    std::cerr <<"New value is smaller than the current value\n";
    return;
  }
  else
  {
    array[index] = value;
    while(index > 0 && array[(index/2) - 1] < array[index])
    {
      std::swap(array[index], array[(index/2) - 1]);
      index = (index/2) - 1;
    }
  }
}

template<typename T>
void max_heap_insert(std::vector<T>& array, T value)
{
  array.resize(array.size() + 1);
  array[array.size() - 1] = -1;
  heap_increase_key(array, array.size() - 1, value);
  build_max_heap(array);
}

int main()
{
std::vector<int> v({1, 2, 6, 3, 7});
build_max_heap(v);
std::cout << "Max-Heap: ";
for(size_t i = 0; i < v.size(); i++)
{
  std::cout << v[i] << " ";
}
std::cout << "\n";
std::cout << "Extract-Maximum: " << heap_extract_max(v) << "\n";
std::cout << "New Heap: ";
for(size_t i = 0; i < v.size(); i++)
{
  std::cout << v[i] << " ";
}
max_heap_insert(v, 10);
std::cout << "\nNew Heap after inserting 10: ";
for(size_t i = 0; i < v.size(); i++)
{
  std::cout << v[i] << " ";
}
std::cout << '\n';
}
\$\endgroup\$
2
\$\begingroup\$

Architecture

The heap should be a class, not a collection of functions:

  • It'll be more convenient to use

  • You can maintain invariants if the actual representation is hidden from the user. You can't do that with a user supplied vector.

Bugs

if(largest != index)
{
    int tmp = array[index];
    array[index] = array[largest];
    array[largest] = tmp;
    max_heapify(array, largest);
}

It's broken if T is not an int. That's not what you want. It should be T tmp. It's even better to use std::swap.

if(array.size() < 0). size is unsigned. It makes absolutely no sense.

array.erase(std::remove(array.begin(), array.end(), array[0], array.end()) - what if there're several values equal to array[0]? Do you want to delete them all? That's not how a priority queue normally works.

Separation of concerns

Don't mix computations and logging.

Efficiency

template<typename T>
void max_heap_insert(std::vector<T>& array, T value)
{
  array.resize(array.size() + 1);
  array[array.size() - 1] = -1;
  heap_increase_key(array, array.size() - 1, value);
  build_max_heap(array);
}

That's very inefficient. You rebuild the heap every time a new value is inserted. A good implementation usually has an O(log N) time complexity per insertion, not O(N).

array.resize(array.size() + 1);
array[array.size() - 1] = -1; 

Just use the std::vector::push_back member-function. It's more efficient and more readable.

\$\endgroup\$
2
\$\begingroup\$

Advice 1

array.shrink_to_fit();: don't do it. If the implementation obeys strictly that request, you will waste a lot CPU cycles.

Advice 2

Whenever you publish your results, make sure that your algorithms/data structures do not write to standard output.

Advice 3

You can micro-optimize your max_heapify. Instead of swapping \$n\$ times, do a shift (see image below). When you have to swap, you sacrifice 3 assignments, so the total work is \$3n\$. If you do a shift instead, you make \$n + 1\$ assignments.

Swapping vs. shifting

Advice 4

T heap_extract_max(std::vector<T>& array)
{
  if(array.size() < 0)
  {
    std::cerr << "Heap Underflow \n";
    return -1;
  }

I believe bad things will happen when T is not an integer.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.