d_mybirthheap.h

是家谱管理系统

#ifndef MYBIRTHHEAP_FUNCTIONS
#define MYBIRTHHEAP_FUNCTIONS

#include <vector>
#include <set>
#include "Person.h"

using namespace std;

//重写了用出生日期为比较对象的函数

bool myBirthcomp(Person a,Person b)
{
	
	if(a.year<b.year)
		return true;
	else if(a.year==b.year)
	{
		if(a.month<b.month)
			return true;
		else if(a.month==b.month)
		{
			if(a.day<b.day)
				return true;
		}
	}
	
	return false;
}
void birexchange(vector<Person>& v,int currentPos,int formerPos);
void myBirthadjustHeap(vector<Person>& v, int first, int last);
void myBirthpopHeap(vector<Person>& v, int last);
void myBirthmakeHeap(vector<Person>& v);

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

void myBirthadjustHeap(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
		// myBirthcomp(v[childPos+1], v[childPos]) is true
		if ((childPos+1 <= last-1) &&
            myBirthcomp(v[childPos+1], v[childPos]))
			childPos = childPos + 1;

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

			v[currentPos] = v[childPos];//赋值，换上去
			birexchange(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 myBirthpopHeap(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];
	birexchange(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)
	myBirthadjustHeap(v, 0, last-1);
}

void myBirthmakeHeap(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)
	{
		myBirthadjustHeap(v,heapPos, lastPos);
		heapPos--;
	}
}
void myBirthheapSort (vector<Person>& v)
{
	// "heapify" the vector v
	myBirthmakeHeap(v);
	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]
		myBirthpopHeap(v, i);
	}
}
#endif	// MYBIRTHHEAP_FUNCTIONS