C++: Maximum Priority Queue

In a Priority Queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

While priority queues are often implemented with heaps, they are conceptually distinct from heaps. [Wikipedia]


Maximum Priority Queue using Heap
Before going through this you should know about Heapsort, because some functions like max_heapify() and build_max_heap() are already discussed there.

parent() returns the parent of the index passed.

int parent(int index)
{
  return (index - 1)/2;
}
 
heap_maximum() returns the maximum element in Θ(1).

T heap_maximum(std::vector<T>& array)
{
  return array[0];
}
 
heap_extract_max() extracts the maximum element i.e pops out the maximum element in O(lg n) time.

T heap_extract_max(std::vector<T>& array)
{
    T max = array[0];
    array[0] = array[array.size() - 1];
    array.resize(array.size() - 1);
    max_heapify(array, 0);
    return max;
}
 
heap_increase_key() repeatedly compares an element to its parent, exchanging their values and continuing if the element's value is larger, and terminating if the element's value is smaller, since the max-heap property hold now. 

It runs in O(lg n) time.

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[parent(index)] < array[index])
    {
      std::swap(array[index], array[parent(index)]);
      index = parent(index);
    }
  }
}
 
max_heap_insert() inserts the element at the correct position using heap_increase_key().

It's running time is O(lg n).

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);
}
 
So a heap can support any priority-queue operations on a set of size n in O(lg n) time.

Here is the program for Priority Queue using Heap

#include <iostream>
#include <vector>

int parent(int index)
{
  return (index - 1)/2;
}

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)
  {
    std::swap(array[index], array[largest]);
    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)
{
    T max = array[0];
    array[0] = array[array.size() - 1];
    array.resize(array.size() - 1);
    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[parent(index)] < array[index])
    {
      std::swap(array[index], array[parent(index)]);
      index = parent(index);
    }
  }
}

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);
}

template<typename T>
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({1, 2, 6, 3, 7});
build_max_heap(v);
std::cout << "Max-Heap: ";
print_heap(v);
std::cout << "\n";
std::cout << "Extract-Maximum: " << heap_extract_max(v) << "\n";
std::cout << "New Heap: ";
print_heap(v);
max_heap_insert(v, 17);
std::cout << "\nNew Heap after inserting 17: ";
print_heap(v);
max_heap_insert(v, 10);
std::cout << "\nNew Heap after inserting 10: ";
print_heap(v);
std::cout
<< '\n';
}
 
You can download this code from here.



Output 



                                                                  
                                                                    
You may also like:
C++: Huffman Coding using STL
C++: Program to find smallest element is an array which is repeated exactly 'k' times
C++: Implementation of Merge Sort
C++: Swapping Node Links in Linked List
C++: Sorting Elements according to Frequency

 




 

Comments