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;
}
선형 힙에 넣었 으면 벡터가 일반 형식으로 저장된다는 의미입니까? 정상적으로는 데이터를 할당 한 사각형의 행으로 그려야합니다. 또한 이진 힙 (binary heap)이라고 할 때마다 이진 트리로 저장합니다.
함수를 구현할 때 일반 벡터 연산자 (푸시 백, 지우기 등)를 사용합니까? 다시 한번, 이것은 숙제입니다.
알려 주셔서 감사합니다. 이것이 내 첫 번째 게시물입니다. – Norava