优先队列(PriorityQueueMax) -- C++实现


实现代码

// PriorityQueueMax.h
#ifndef PRIORITYQUEUEMAX_H
#define PRIORITYQUEUEMAX_H

#include<iostream>
#include "Component.h"
using namespace std;

namespace jay{
	template<typename T>
	class PriorityQueueMax
	{
	public:
		PriorityQueueMax(int maxsize = 100);
		PriorityQueueMax(T* array,int nSize);
		PriorityQueueMax(const PriorityQueueMax<T>& rhs);
		PriorityQueueMax<T>& operator=(const PriorityQueueMax<T>& rhs);
		~PriorityQueueMax();

		void Insert(const T data);
		void Swim(int k);
		void Sink(int k);
		T PopMax();
		void Resize(int size);
		void PrintElements();
		bool isMaxHeap(int k);
		bool isMaxHeap();

		T  Max() const;

		bool IsEmpty() const;
		int Size() const;

	private:
		// 存放T的内存区域
		T *m_array;
		int m_nSize;
		// 当前队列的大小[动态变化]
		int m_ncapacity;
	};

	template<typename T>
	PriorityQueueMax<T>::PriorityQueueMax(int nMaxsize) :m_ncapacity(nMaxsize)
	{
		m_array = NULL;
		m_array = new T[nMaxsize+1];
		if (m_array == NULL)
		{
			throw "Failed to allocate memory!";
		}
		m_nSize = 0;
	}

	template<typename T>
	PriorityQueueMax<T>::PriorityQueueMax(T* array,int nSize) :m_ncapacity(nSize),m_nSize(nSize)
	{
		m_array = new T[nSize+1];
		if (m_array == NULL)
		{
			throw "Failed to allocate memory!";
		}

		for (int i=0;i<m_nSize;i++)
		{
			m_array[i+1] = array[i];
		}

	}

	template<typename T>
	void PriorityQueueMax<T>::Insert(const T data)
	{
		if (m_nSize == m_ncapacity)
			Resize(m_ncapacity*2);
		    
		m_array[++m_nSize] = data; 
		Swim(m_nSize);
	}

	template<typename T>
	void PriorityQueueMax<T>::Resize(int size)
	{
		if (m_nSize > size)
		    return;

		T *newbuf = new T[size+1];

		if (newbuf == NULL)
		{
			throw "Failed to allocate memory!";
		}

		for (int i=0;i<=m_nSize;i++)
		{
			newbuf[i] = m_array[i];
		}

		delete []m_array;
		m_array = newbuf;
		m_ncapacity = size;
	}

	// [上浮]调整父节点
	template<typename T>
	void PriorityQueueMax<T>::Swim(int k)
	{
		// k>1且如果k的父节点小于K,则交换k和k的父节点
		while (k > 1 && m_array[k/2] < m_array[k]) 
		{
			ExchangeArrayElements(m_array,k, k/2);
			k = k/2;
		}
	}

	// [下沉]调整子节点
	template<typename T>
	void PriorityQueueMax<T>::Sink(int k)
	{
		while (2*k <= m_nSize) 
		{
			// k的左子节点
			int leftnode = 2*k;

			// 比较左/右节点 找出较大的节点
			if (leftnode < m_nSize && m_array[leftnode] < m_array[leftnode+1]) 
				leftnode++;
			// 比较父节点与较大的子节点
			if (m_array[k] > m_array[leftnode])
				break;
			// 如果左/右子节点比父节点大,则交换他们的子
			ExchangeArrayElements(m_array,k, leftnode);

			k = leftnode;

		}
	}

	template<typename T>
	bool PriorityQueueMax<T>::IsEmpty() const
	{
		return m_nSize == 0;
	}

	template <typename T>
	T PriorityQueueMax<T>::PopMax()
	{
		if (IsEmpty())
			throw "empty Queue";

		T max = m_array[1];
		ExchangeArrayElements(m_array,1,m_nSize--);
		Sink(1);

		if ((m_nSize > 0) && (m_nSize == (m_ncapacity) / 4)) 
			Resize(m_ncapacity / 2);

		return max;
	}

	template<typename T>
	bool PriorityQueueMax<T>::isMaxHeap()
	{
		return isMaxHeap(1);
	}

	template<typename T>
	bool PriorityQueueMax<T>::isMaxHeap(int k)
	{
		// k是父节点
		if (k > m_nSize)
		    return true;

		// 左子节点
		int left = 2 * k;
		// 右子节点
		int right = 2 * k + 1;

		if (left < m_nSize && m_array[left] > m_array[k])
			return false;

		if (right < m_nSize && m_array[right] > m_array[k])
			return false;

		// 递归判断子节点
		return isMaxHeap(left) && isMaxHeap(right);
	}

	template <typename T>
	T PriorityQueueMax<T>::Max() const
	{
		if (IsEmpty())
			throw "empty Queue";

		return m_array[1];
	}

	template<typename T>
	void PriorityQueueMax<T>::PrintElements()
	{
		for (int i=1;i<=m_nSize;i++)
		{
			cout << m_array[i] << " ";
		}
		cout<< endl;
	}

	template<typename T>
	PriorityQueueMax<T>::~PriorityQueueMax()
	{
		delete[] m_array;
	}
};

#endif

测试代码

//main.cpp

#include <time.h>
#include<windows.h>

#include <iostream>
#include <vector>
using namespace std;

#include "Component.h"
#include "Queue.h"
#include "PriorityQueueMax.h"

using namespace jay;


int main(int argc, char* argv[])
{
	PriorityQueueMax<int> myqueue(testarray); // 声明队列

	int nSize;
	cin >> nSize;

	int p;
	TimeCalculator timec;
	while(cin>>p)
	{
		myqueue.Insert(p);
	}
	cout << "堆初始化";
	timec.PrintTimeInfo();

//	myqueue.PrintElements();

	cout << "最大堆?" << myqueue.isMaxHeap() << endl;

	for (int i=0;i<100;i++)
	{
		if(!myqueue.IsEmpty())
		{
			timec.RestartBegin();
			cout << "当前出队列元素: " << myqueue.PopMax() <<endl;
			timec.PrintTimeInfo();
		}
	}

	cout <<endl;
	timec.RestartBegin();
	myqueue.Insert(1232344);
	timec.PrintTimeInfo();


	timec.RestartBegin();
	myqueue.Insert(34);
	timec.PrintTimeInfo();

	timec.RestartBegin();
	myqueue.Insert(10000);
	timec.PrintTimeInfo();


	timec.RestartBegin();
	myqueue.Insert(9999999);
	timec.PrintTimeInfo();

	timec.RestartBegin();
	myqueue.Insert(0);
	timec.PrintTimeInfo();

	while(myqueue.IsEmpty())
	{
		myqueue.PopMax();
	}
}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。