I'm working on making a minimum priority queue. We were provided a template to use that has originated some questions. Here are the two codes.
This is the header file.
#ifndef _PRIORITY_QUEUE_
#define _PRIORITY_QUEUE_
template <typename _T> struct element
{
typedef _T data_type ;
element () {}
element (int _k, const _T & _e) : m_key (_k), m_element (_e) {}
int m_key ;
data_type m_element ;
} ;
/*
* compare keys of _e1 and _e2
*/
template <typename _T> bool operator < (const element<_T> & _e1, const element<_T> & _e2)
{
return _e1.m_key < _e2.m_key ;
}
template <typename _T> std::ostream & operator << (std::ostream & os, const element<_T> & _e)
{
std::cout<<'['<<_e.m_key<<','<<_e.m_element<<']'<<std::endl;
return os ;
}
/**
* Linear data structure implementation
* _E is the element type
*/
template <typename _E>
class linear_heap
{
public :
typedef _E element_type ;
typedef typename _E::data_type data_type;
linear_heap (int _s = 100)
{
allocate_memory(_s);
this->m_size = 0;
}
unsigned size () const {return this->m_size ; }
element_type & get_min () throw (const char *)
{
if (true == is_empty()) throw ("Empty heap");
return m_array[0] ;
} ;
void insert_element (const element_type & _e)
{
// implement
}
void delete_min () throw (const char * )
{
if (true == is_empty()) throw ("Empty heap");
// implement
}
public :
void update_element (element_type & _e, int _k)
{
// implement
}
void build_heap ()
{
// implement
}
void remove_element (element_type & _e)
{
// implement
}
bool is_empty ()
{
return (0 == m_size );
}
void allocate_memory (unsigned _s)
{
this->m_capacity = _s;
this->m_array.resize (this->m_capacity);
}
protected :
unsigned m_capacity ; // The capacity of m_array
unsigned m_size ; // The number of current elements
// implement
// choose one of the following data structure.
std::vector<element_type> m_array ; // Storage of elements
// std::list<element_type> m_array ; // Storage of elements
} ;
/**
* Binary heap implementation
* _E is the element type
*/
template <typename _E>
class binary_heap
{
public :
typedef _E element_type ;
typedef typename _E::data_type data_type;
binary_heap (int _s = 100)
{
allocate_memory(_s);
this->m_size = 0;
}
unsigned size () const {return this->m_size ; }
element_type & get_min () throw (const char *)
{
if (true == is_empty()) throw ("Empty heap");
return m_array[0] ;
} ;
element_type & operator [] (unsigned id)
{
return m_array[id] ;
}
void insert_element (const element_type & _e)
{
// implement
}
void delete_min () throw (const char * )
{
if (true == is_empty()) throw ("Empty heap");
// implement
}
public :
void update_element (element_type & _e, int _k)
{
// implement
}
void build_heap ()
{
// implement
}
void remove_element (element_type & _e)
{
// implement
}
bool is_empty ()
{
return (0 == m_size );
}
void allocate_memory (unsigned _s)
{
this->m_capacity = _s;
this->m_array.resize (this->m_size);
}
protected :
unsigned m_capacity ; // The capacity of m_array
unsigned m_size ; // The number of current elements
std::vector<element_type> m_array ; // Storage of elements
} ;
/**
* _H is the heap type. Could be array, list or binary heap.
*
*/
template <typename _H> class priority_queue
{
public :
typedef typename _H::element_type element_type ;
typedef typename _H::data_type data_type ;
typedef _H heap_type ;
void insert (int _key, const data_type & _value)
{
m_heap.insert_element (element_type (_key, _value));
}
element_type & min ()
{
return m_heap.get_min();
}
element_type & get_loc (unsigned id)
{
return m_heap[id] ;
}
void createPriorityQueue ()
{
m_heap.build_heap ();
}
void decreaseKey (element_type & _e, int _k)
{
m_heap.update_element (_e, _k) ;
}
void remove (element_type & _e)
{
m_heap.remove_element(_e) ;
}
unsigned size () const
{
return m_heap.size();
}
bool isEmpty()
{
return m_heap.is_empty();
}
protected :
heap_type m_heap ;
} ;
template <typename _H> std::istream & operator >> (std::istream & is, priority_queue <_H> & _p)
{
typedef typename _H::element_type element_type ;
typedef typename _H::data_type data_type ;
int key ;
data_type value ;
while (std::cin>>key>>value)
{
_p.insert (key, value) ;
}
return is ;
}
#endif
Here is the main file.
#include <vector>
#include <list>
#include <string>
#include <iostream>
#include "priority_queue.h"
int main()
{
try
{
priority_queue<linear_heap<element<std::string> > > string_linear_heap ;
// create the binary heap .
priority_queue<binary_heap<element<std::string> > > string_binary_heap ;
std::cin>>string_binary_heap ;
string_binary_heap.createPriorityQueue() ;
// Decrease the key of the first element by 2.
// You may output the cost of decreaseKey here.
string_binary_heap.decreaseKey (string_binary_heap.get_loc(0), string_binary_heap.get_loc(0).m_key - 2);
// Try to pop up elements in order w.r.t. their keys.
while (!string_binary_heap.isEmpty())
{
element <std::string> & loc = string_binary_heap.min() ;
std::cout<<loc<<std::endl;
// You may output the cost of remove here.
string_binary_heap.remove(loc);
}
}
catch (const char * msg)
{
std::cerr<<" [EXCEPTION] "<<msg<<std::endl;
}
return 0;
}
When they have you put it in a linear heap, does that mean the vector is stored in a normal format? By normal, I mean picturing it as a row of squares with data assigned. Also, whenever it says binary heap, that stores it as a binary tree?
When implementing the functions, do you use normal vector operators (pushback, erase, etc.)? Once again, this is homework.
