1
我正在制定最小優先級隊列。我們提供了一個使用的模板，它引發了一些問題。這是兩個代碼。最小優先級隊列模板
這是頭文件。
#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
這裏是主文件。
#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;
}
當他們你把它放在一個線性堆中，這是否意味着矢量以正常格式存儲？正常情況下，我的意思是把它描繪成一排分配數據的正方形。此外，每當它說二進制堆，它將其存儲爲二叉樹？
實現函數時，是否使用法向量運算符（推回，擦除等）？再次，這是作業。
感謝您告訴我，這是我的第一篇文章。 – Norava