Kafka tws mirror maven ipv4 Gradle inheritance parameters odbc Semantic UI LimeJS 八大员 pmp视频 jquery遍历子元素 鼠标进入和离开事件 matlab中log函数 matlab不等于 数据库查询 mysql临时表 python对象 python的def python开发界面 java数组添加元素 java数据类型转换 linux启动 python下载教程 服务器系统下载 图片链接生成器 战地联盟辅助 netreflector kontakt 微信临时链接多久失效 php小数点保留2位 小程序游戏源码 五笔字型86版 模拟邻居 ps祛痘 ps怎么p人脸 易语言tv ps阵列 机箱最佳风道图
当前位置: 首页 > 学习教程  > 编程语言

数据结构——最小堆

2021/2/13 17:26:07 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

优先队列懒得打了 #include <iostream> //#include<priority_queue> using namespace std; const int DefaultSize10;template<class T> class MinHeap { public:MinHeap(int sz DefaultSize); //构造函数&#xff1a;建立空堆MinHeap(T arr[], int n); …

优先队列懒得打了

#include <iostream>
//#include<priority_queue>
using namespace std; 
const int DefaultSize=10;

template<class T>
class MinHeap {
public:
	MinHeap(int sz = DefaultSize);	//构造函数:建立空堆
	MinHeap(T arr[], int n);		//构造函数:通过一个数组创建堆
	~MinHeap() { delete[] heap; }	//析构函数
	bool insert(const T& x);		//将x插入到最小堆中
	bool removeMin(T& x);			//删除堆顶元素(min value)
	bool isTmpty() const;			//判断堆是否是空
	bool isFull() const;			//判断堆是否已满
	void makeTmpty();				//置空堆 
	void output();					//数组元素输出
private:
	T* heap;						//存放最小堆元素的数组
	int currentSize;				//最小堆中当前元素的个数
	int maxHeapSize;				//最小堆最多存放元素个数
	void siftDown(int start, int m);//从start到m下滑调整为最小堆
	void siftUp(int start);			//从start到0上滑调整为最小堆
};


template<class T>
MinHeap<T>::MinHeap(int sz) {
	maxHeapSize = (DefaultSize < sz) ? sz : DefaultSize;
	heap = new T[maxHeapSize];
	if (heap == NULL) {
		cerr << "内存分配失败" << endl;
		exit(1);
	}
	currentSize = 0;
}

template<class T>
MinHeap<T>::MinHeap(T arr[], int n) {
	maxHeapSize = (DefaultSize < n) ? n : DefaultSize;
	heap = new T[maxHeapSize];
	if (heap == NULL) {
		cerr << "内存分配失败" << endl;
		exit(1);
	}
	for (int i = 0; i < n; i++) {
		heap[i] = arr[i];							
	}
	currentSize = n;
	//利用完全二叉树中元素的排列规律,找到最初调整位置,也就是最后的分支节点
	int currentPos = (currentSize - 1) / 2;
	while (currentPos >= 0) {						
		siftDown(currentPos, currentSize - 1);		
		currentPos--;								
	}
}

template<class T>
void MinHeap<T>::output() {
	for (int i = 0; i < currentSize; i++) {
		cout << heap[i] << ' ';
	}
}

template<class T>
bool MinHeap<T>::isTmpty() const {
	return (0 == currentSize) ? true : false;
}

template<class T>
bool MinHeap<T>::isFull() const {
	return (maxHeapSize == currentSize) ? true : false;
}

template<class T>
void MinHeap<T>::makeTmpty() {
	currentSize = 0;
}

template<class T>
bool MinHeap<T>::insert(const T& x) {
	if (isFull()) {									//判断堆是否已经满
		cerr << "Heap Fulled" <<  endl;
		return false;								
	}
	heap[currentSize] = x;							//将x元素插入到数组最后
	siftUp(currentSize);
	currentSize++;									//对当前大小增加1
	return true;
}

template<class T>
bool MinHeap<T>::removeMin(T& x) {
	if (0 == currentSize) {
		cout << "Heap Tmptyed" << endl;
		return false;
	}
	x = heap[0];
	heap[0] = heap[currentSize - 1];
	currentSize--;
	siftDown(0, currentSize - 1);					//借助函数对堆再一次调整
	return true;
}

template<class T>
void MinHeap<T>::siftDown(int start, int m) {
	int i = start;
	int j = 2 * i + 1;								//通过公式2x+1求得x左子女位置
	T temp = heap[i];								//temp记录原来的的数据
	while (j <= m) {
		if (j < m && heap[j] > heap[j + 1]) {
			j = j + 1;								//j指向左右子女中较小的一个
		}
		if (heap[j] >= temp) {
			break;									
		}
		else {									
			heap[i] = heap[j];
			i = j;
			j = 2 * i + 1;
		}
	}
	heap[i] = temp;									
}

template<class T>
void MinHeap<T>::siftUp(int start) {
	int j = start;
	int i = (j - 1) / 2;
	T temp = heap[j];
	while (j > 0) {
		if (heap[i] <= temp) {
			break;
		}
		else {
			heap[j] = heap[i];
			j = i;
			i = (j - 1) / 2;
		}
	}
	heap[j] = temp;
}

int main()
{
	
	return 0;
}



本文链接: http://www.dtmao.cc/news_show_700143.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?