算法导论Problem6-3 Youngtableau问题 堆排序应用
这道题大概就是要实现一个数组，这个数组中行所有元素都有序，列所有元素都有序。
其实这也是应用堆排序的思想，就是把这个数组的看做是二叉树组成的。一个元素的下面一行的对应一个元素是它的左孩子，右边一个元素是它的右孩子。
这样就可以应用堆排序来解决这个问题了。
同时也是像堆排序一样，实际使用一维数组存储数据，人为规定（按照堆排序的规则，这个是关键思维）地构造二维数组来存储二叉树。
详细程序如下：
#include<iostream>#include<vector>using namespace std;int gChildren = 2;int column = 4;//实际用以为数组表示数据，但是通过人为地规定，构造了一个二维数组，同理可以很轻松地构造三维数组//主要不同之处就是寻找孩子和父母节点不一样了int youngTableauUpParent(int cIndex)//cIndex 为C下标0开始{return cIndex-column;}int youngTableauleftParent(int cIndex){return cIndex-1;}int youngTableauChild(int cIndex, int leftOrRight)//cIndex 为C下标0开始{if(leftOrRight==1)//代表左孩子return cIndex+column;else //代表是右孩子return cIndex+1;}//找出当前节点和其孩子们的当中的最大值;//本人觉得是本人创造的非常妙的从youngTableauify函数中分离出来的功能函数。极大的简化了对本算法的理解。template<typename T>int youngTableauMax(vector<T>& youngTableau, int cIndex, int youngTableauSize){T tempMax = youngTableau[cIndex];int childIndex = 0;int tempIndex = cIndex;//不同处：如果是最右一列就没有右孩子，如果是最下面一行就没有左孩子，就直接跳过if(youngTableauChild(cIndex, 1)<youngTableauSize) {childIndex = youngTableauChild(cIndex, 1);//1代表左孩子if(youngTableau[childIndex]>tempMax){tempMax = youngTableau[childIndex];tempIndex = childIndex;}}//注意：少了第二个判断条件会出现错误结果，而且很难Debug。千万不能漏了条件if((cIndex+1)%column!=0 && (cIndex+1)<youngTableauSize){childIndex = youngTableauChild(cIndex, 2);//2代表右孩子if(youngTableau[childIndex]>tempMax){tempMax = youngTableau[childIndex];tempIndex = childIndex;}}return tempIndex;}//与堆排序一模一样//We assume cIndex's children have all been youngTableauified, which is the key to make this algorithm work!!!//比之前的二叉树堆排序更加简洁明了点template<typename T>void youngTableauify(vector<T>& youngTableau, int cIndex, int youngTableauSize){if(cIndex<youngTableauSize){int tempIndex = youngTableauMax(youngTableau, cIndex, youngTableauSize);if(tempIndex != cIndex){swap(youngTableau[cIndex], youngTableau[tempIndex]);youngTableauify(youngTableau, tempIndex, youngTableauSize); }}}template<typename T>void buildMaxyoungTableau(vector<T>& youngTableau){for(int i=(youngTableau.size()-1); i>=0; i--)//不同处：从下表倒数第二个开始youngTableauify(youngTableau, i, youngTableau.size());}//与堆排序一模一样template<typename T>void youngTableauSort(vector<T>& youngTableau){buildMaxyoungTableau(youngTableau);for(int i=youngTableau.size()-1; i>0; i--){swap(youngTableau[0], youngTableau[i]);youngTableauify(youngTableau, 0, i);}}template<typename T>void youngTableauPrint(const vector<T>& youngTableau){int i = 1;for(auto x:youngTableau){cout<<x<<"\t";if(i%column==0) cout<<endl;i++;//输出格式化的数组，方便检查}cout<<endl;}void test(){//初始化数组int a[15] = {2,4,7,1,4,8,9,31,83,28,48,94,87,16,36};vector<int> youngTableau(a, a+15);//序列输出cout<<"Befor build youngTableau:\n";youngTableauPrint(youngTableau);//建立大顶堆后输出cout<<"After build youngTableau:\n";buildMaxyoungTableau(youngTableau);youngTableauPrint(youngTableau);//排序后cout<<"After sort:\n";youngTableauSort(youngTableau);youngTableauPrint(youngTableau);}int main(){test();return 0;}
结果：
可以改变column，以改变列数，来看看结果如何，而且最后一行可以是不满列，列如本例中column等于4的时候：
column = 3:
column = 4:
可以是任意列数，甚至可以是column=1，column=100，会有有趣的结果哦，呵呵。有兴趣的可以试一试，想想为什么。