[Day17]程序菜鸟自学C++资料结构演算法 – 堆积实作与应用

前言：昨天讲解完了堆积的概念，今天要来实际操作一遍，在查找资料之余，有发现一个有趣的ACM程序竞赛题，实作完堆积後会顺便介绍给各位看看。

堆叠的向下调整：

昨天有提到堆积调整的概念及方法，现在就是要来实践的时候！

向下调整通常在一开始建立堆积的时候或删除元素的时候会执行。

可以看到堆积内的元素已经调整完成，详细图形如下。

撰写好向下调整的方法後，还可以再写一个把杂乱无章的数组调整成堆积的方法。

接着来写删除元素的方式，并直接调整维持堆叠的规则。

再来撰写新增元素的方法，且直接向上调整成堆叠。

输出结果，第一行为原本的堆叠，第二行为新增11，第三行则删除堆叠顶端。

利用堆叠实作优先伫列：

掌握了堆叠，接着可以练习看看优先伫列的建立。
提示：把堆叠想像成优先伫列，新增就是push，删除就是pop，堆叠顶端就是最优先元素。直接往下继续写就好oUo

这样就不需依靠C++内部的程序完成优先伫列。

ACM竞赛题 – 聪明的木匠：在查找资料过程中，意外找到了着个题目，就顺便分享一下
题目内容：一位木匠需要将一根长的木棒切成N段。每段的长度分别为L1,L2,......,LN（1 <= L1,L2,…,LN <= 1000，且均为整数）个长度单位，且切割时仅在整数点处切且没有木材损失。
木匠发现，每一次切割花费的体力与该木棒的长度成正比，设切割长度为1的木棒花费1单位体力。例如：若N=3，L1 = 3,L2 = 4,L3 = 5，则木棒原长为12，木匠可以有多种切法，如：先将12切成3+9.，花费12体力，再将9切成4+5，花费9体力，一共花费21体力；还可以先将12切成4+8，花费12体力，再将8切成3+5，花费8体力，一共花费20体力。显然，後者比前者更省体力。那麽，木匠至少要花费多少体力才能完成切割任务呢？

执行结果如下，第一行为n的值，第二行为每此切割次数的长度，接着就是计算结果。

本日小结：今天也是非常充实的一天，终於结束了堆叠的部分，下一次提到大概就是演算法的时候了，木匠的程序码虽然不长，但是要理解题目的内容就要花点时间了，如果还是不懂也没关系，先把基础的弄明白就好了⋋╏ ❛ ◡ ❛ ╏⋌

堆积

#include <vector>
#include <iostream>
using namespace std;
template<typename T>
void down_adjust(vector<T> & data, int s) { //从下标为s的元素开始调整
	int n = data.size();
	if (n == 0) return;
	T t = data[s];  //把s节点的资料放入t元素变量内，表示s最後的去处
	int m = n - 1; //对元素进行移动
	for (int j = 2 * s + 1; j < n;) { //先找到s的左子节点{j = 2 * s + 1}
		if (j < m && data[j] < data[j + 1]) //j可想成节点的编号，data[j]则是节点内的资料
			j++; //j指向较大的子节点
		if (!(t < data[j])) break; //如果t(data[s])没有小於data[j]，则跳出回圈
		data[s] = data[j]; //接着开始移动元素和指标
		s = j; j = 2 * j;
	}
	data[s] = t;
}
template<typename T>
void make_Heap(vector<T> &data) { //建立堆积
	for (int s = (data.size() - 1 - 1) / 2; s >= 0; s--)
		down_adjust(data, s);
}
template<typename T>
void pop_Heap(vector<T>& data) { //删除元素
	swap(data[0], data[data.size() - 1]); //swap用来交换两边量的值
	data.pop_back();
	down_adjust(data, 0);
}
template<typename T>
void push_Heap(vector<T>& data,const T e) { //新增元素至堆叠最末端，并向上调整
	data.push_back(e);
	int s = data.size() - 1;
	T t = data[s]; //和向下调整的过程类似
	for (int j = floor((s - 1.) / 2); j >= 0;) { //floor为取整数的意思
		if (t < data[j]) break;
		data[s] = data[j];
		s = j; j = floor((s - 1.) / 2);
	}
	data[s] = t;
}

int main() {
	/*vector<int> a{ 7,9,6,8,1,4,2,3 };
	down_adjust(a, 0);
	for (auto e : a)
		std::cout << e << " ";*/
	vector<int> a{ 7,19,6,8,1,5,4,2 };
	make_Heap(a);
	for (auto e : a)
		std::cout << e << " ";
	std::cout << endl;

	push_Heap(a, 11);
	for (auto e : a)
		std::cout << e << " ";
	std::cout << endl;

	pop_Heap(a);
	for (auto e : a)
		std::cout << e << " ";
	std::cout << endl;
}

优先伫列

#include <vector>
#include <iostream>
using namespace std;
template<typename T>
void down_adjust(vector<T>& data, int s) { //从下标为s的元素开始调整
	int n = data.size();
	if (n == 0) return;
	T t = data[s];  //把s节点的资料放入t元素变量内，表示s最後的去处
	int m = n - 1; //对元素进行移动
	for (int j = 2 * s + 1; j < n;) { //先找到s的左子节点{j = 2 * s + 1}
		if (j < m && data[j] < data[j + 1]) //j可想成节点的编号，data[j]则是节点内的资料
			j++; //j指向较大的子节点
		if (!(t < data[j])) break; //如果t(data[s])没有小於data[j]，则跳出回圈
		data[s] = data[j]; //接着开始移动元素和指标
		s = j; j = 2 * j;
	}
	data[s] = t;
}
template<typename T>
void make_Heap(vector<T>& data) { //建立堆积
	for (int s = (data.size() - 1 - 1) / 2; s >= 0; s--)
		down_adjust(data, s);
}
template<typename T>
void pop_Heap(vector<T>& data) { //删除元素
	swap(data[0], data[data.size() - 1]);
	data.pop_back();
	down_adjust(data, 0);
}
template<typename T>
void push_Heap(vector<T>& data, const T e) { //新增元素至堆叠最末端，并向上调整
	data.push_back(e);
	int s = data.size() - 1;
	T t = data[s]; //和向下调整的过程类似
	for (int j = floor((s - 1.) / 2); j >= 0;) { //floor为取整数的意思
		if (t < data[j]) break;
		data[s] = data[j];
		s = j; j = floor((s - 1.) / 2);
	}
	data[s] = t;
}

template<class T>
class priority_queue {
	vector<T> data;
public:
	void push(const T& e) {
		push_Heap(data, e);
	}
	void pop() {
		pop_Heap(data);
	}
	T top() {
		if (empty()) throw "伫列为空"; return data[0];
	}
	bool empty() {
		return data.size() == 0;
	}
	void clear() {
		data.clear();
	}
	int size() {
		return data.size();
	}
};
template<typename T>
void heapsort_down_adjust(vector<T>& data, int s,int m) { //从下标为s的元素开始调整
	T t = data[s];  //把s节点的资料放入t元素变量内，表示s最後的去处
	for (int j = 2 * s + 1; j <= m;) { //先找到s的左子节点{j = 2 * s + 1}
		if (j < m && data[j] < data[j + 1]) //j可想成节点的编号，data[j]则是节点内的资料
			j++; //j指向较大的子节点
		if (!(t < data[j])) break; //如果t(data[s])没有小於data[j]，则跳出回圈
		data[s] = data[j]; //接着开始移动元素和指标
		s = j; j = 2 * j;
	}
	data[s] = t;
}
template<typename T>
void heap_sort(vector<T>& data){
	int n = data.size();
	for (int s = floor((data.size() - 1 - 1) / 2); s >= 0; s--) //建立堆叠
		heapsort_down_adjust(data, s, n - 1); //s~n-1之间
	for (int i = n - 1; i > 0; i--) {
		swap(data[0], data[i]); //交换两元素
		heapsort_down_adjust(data, 0, i - 1); //0~i-1之间
	}
}
int main() {
	/*priority_queue<int> q;
	q.push(5);
	q.push(2);
	q.push(7);
	q.push(9);
	q.push(4);
	cout << "伫列元素各数：" << q.size() << endl;
	while (!q.empty()) {
		cout << q.top() << " "; q.pop();
	}
	cout << endl;
	return 0;*/

	vector<int> a{ 7,9,2,8,1,4,6,3 };
	heap_sort(a);
	for (auto e : a)
		std::cout << e << " ";
	std::cout << endl;
}

聪明的木匠

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

int main() {
	std::priority_queue<int, std::vector<int>, std::greater<int> >q;
	//因为每此都要先取小的，所以使用优先伫列
	int n;
	while (cin >> n) { //输入n，为要切几此
		for (int i = 0; i < n; i++) {
			int key; //key为每次切割的长度
			std::cin >> key;
			q.push(key); //放入伫列
		}
		int sum = 0;
		while (n >= 2) {
			int a, b;
			a = q.top(); //先从伫列取一个最小的
			q.pop();
			b = q.top(); //在取第二小的
			q.pop();
			q.push(a + b); //把相加的结果在放入伫列中
			sum += a + b; //因为相加的结果必须要参加下一阶段
			cout << a << " " << b << " " << sum << std::endl;
			n--; //每执行完一次循环就将n-1
		}
		cout << sum << endl;
	}
	return 0;
}