[데이터 구조] Priorityqueue (우선 순위 대기 열)

2254 단어
//.h
const int MAX_LEN = 100;
template
class p_queue
{
public:
	p_queue();
	bool full();
	bool empty();
	int size();
	void clear();
	void insert(const List_entry ¤t);
	void remove();
	void creation();
	void print();

private:
	int count;
	List_entry entry[MAX_LEN];
	void insert_heap(const List_entry ¤t, int low, int high);
};
//.cpp
#include
#include"p_queue.h"
using namespace std;

template
p_queue::p_queue()
{
	count = 0;
}

template
bool p_queue::full()
{
	return count==MAX_LEN;
}

template
bool p_queue::empty()
{
	return count==0;
}

template
int p_queue::size()
{
	return count;
}

template
void p_queue::clear()
{
	count = 0;
}

template
void p_queue::insert(const List_entry ¤t)
{
	entry[size()] = current;
	count++;
	creation();
}

template
void p_queue::insert_heap(const List_entry & current, int low, int high)
{
	int large = 2 * low + 1;
	while (large <= high) {
		if (large < high&&entry[large] < entry[large + 1])
			large++;		//   large        
		if (entry[large] < current)break;
		else {				//promote entry[large]
			entry[low] = entry[large];
			low = large;
			large = 2 * low + 1;
		}
	}
	entry[low] = current;

}

template
void p_queue::remove()
{
	for (int i = 0; i < size()-1; i++) {
		entry[i] = entry[i + 1];
	}
	count--;
	creation();
}

template
void p_queue::creation()
{
	for (int low = count / 2 - 1; low >= 0; low--) {
		List_entry current = entry[low];
		insert_heap(current, low, count - 1);
	}
}

template
void p_queue::print()
{
	for (int i = 0; i < size(); i++)
		cout << entry[i] << ' ';
	cout << endl;
}

좋은 웹페이지 즐겨찾기