d_mynameheap.h

是家谱管理系统

#ifndef MYNAMEHEAP_FUNCTIONS
#define MYNAMEHEAP_FUNCTIONS

#include <vector>
#include <set>
#include "Person.h"
using namespace std;


//重写了用姓名为比较对象的函数

bool myNamecomp(Person a,Person b)
{
	
	if(strcmp(a.name,b.name)<0)
		return true;
	else 
		return false;
}
//v[formerPos]移动到v[currentPos] 他的父亲childrenID[]的变化和他的小孩parentID的变化

void naexchange(vector<Person>& v,int currentPos,int formerPos);
void myNameadjustHeap(vector<Person>& v, int first, int last);
void myNamepopHeap(vector<Person>& v, int last);
void myNamemakeHeap(vector<Person>& v);

//v[formerPos]移动到v[currentPos] 他的父亲childrenID[]的变化和他的小孩parentID的变化
void naexchange(vector<Person>& v,int currentPos,int formerPos)
{
	int n=v.size(),i;
	for(i=0;i<n;i++)
		if(v[i].parentID==formerPos)
			v[i].parentID=currentPos;
}

void myNameadjustHeap(vector<Person>& v, int first, int last)
{
	int currentPos, childPos;
	Person target;

	// start at first and filter target down the heap
	currentPos = first;
	target = v[first];
	set<int>child;//把v[first] 的小孩的ID都存入child集合中
	for(int i=0;i<v.size();i++)
		if(v[i].parentID==first)
			child.insert(i);
	// compute the left child index and begin a scan down
	// path of children, stopping at end of list (last)
	// or when we find a place for target
	childPos = 2 * currentPos + 1;
	while (childPos <= last-1)
	{
		// index of right child is childPos+1. compare the
		// two children. change childPos if
		// myNamecomp(v[childPos+1], v[childPos]) is true
		if ((childPos+1 <= last-1) &&
            myNamecomp(v[childPos+1], v[childPos]))
			childPos = childPos + 1;

		// compare selected child to target
		if (myNamecomp(v[childPos],target))
		{
			// myNamecomp(selected child, target) is true.
			// move selected child to the parent;
			// position of selected child is now vacated

			v[currentPos] = v[childPos];//赋值，换上去
			naexchange(v,currentPos,childPos);
			if(child.erase(childPos)==1)
				child.insert(currentPos);
			if(target.parentID==childPos)
				target.parentID=currentPos;
			// update indices to continue the scan
			currentPos = childPos;
			childPos = 2 * currentPos + 1;
		}
		else
			// target belongs at currentPos
			break;
	}
	v[currentPos]=target;
	set<int>::iterator iter;
	for(iter=child.begin();iter!=child.end();iter++)//把他小孩的patentID改为currentPos
		v[*iter].parentID=currentPos;
}

void myNamepopHeap(vector<Person>& v, int last)
{
	Person temp;
	set<int>child;//把v[0] 的小孩的ID都存入child向量中
	for(int i=0;i<v.size();i++)
		if(v[i].parentID==0)
			child.insert(i);
	// exchange the first and last element in the heap
	temp = v[0];
	v[0] = v[last-1];
	naexchange(v,0,last-1);
	if(child.erase(last-1)==1)
		child.insert(0);
	if(temp.parentID==last-1)
		temp.parentID=0;
	v[last-1] = temp;
	set<int>::iterator iter;
	for(iter=child.begin();iter!=child.end();iter++)//把他小孩的patentID改为currentPos
		v[*iter].parentID=last-1;
	// filter down the root over the range [0, last-1)
	myNameadjustHeap(v, 0, last-1);
}

void myNamemakeHeap(vector<Person>& v)
{
	int heapPos, lastPos;

	// compute the size of teh heap and the index
	// of the last parent
	lastPos = v.size();
	heapPos = (lastPos - 2)/2;

	// filter down every parent in order from last parent
	// down to root
	while (heapPos >= 0)
	{
		myNameadjustHeap(v,heapPos, lastPos);
		heapPos--;
	}
}
void myNameheapSort (vector<Person>& v)
{
	// "heapify" the vector v
	myNamemakeHeap(v);
	//cout<<"&&&&&&&&"<<endl;
	//for(int k=0;k<v.size();k++)
		//v[k].outputPerson();
	int i, n = v.size();

	// iteration that determines elements v[n-1] ... v[1]
	for(i = n; i > 1;i--)
	{
		// call popHeap() to move next largest to v[n-1]
		myNamepopHeap(v, i);
		//cout<<"%%%%"<<endl;
		//for(int h=0;h<v.size();h++)
		//v[h].outputPerson();
	}
}
#endif	// MYNAMEHEAP_FUNCTIONS