binaryheap.h

binaryheap

#ifndef BINARYHEAP_H
#define BINARYHEAP_H
#include <math.h>
#include <iostream>
#include <string>
using namespace std;

typedef struct
{
	int firstvex;
	int lastvex;
	int time;
}num;
typedef struct  
{
    int size ;
	num *element;
}HEAP;
/*插入最小元素*/
void heapinsert(HEAP &heap,num);

/*删除最小元素*/
num heapdelete(HEAP &heap);
/*比较第一个数是不是比第二个数大*/
bool GT(num,num);
/*比较两个数相等*/
bool EQU(num,num);
/*比较第一个数是不是比第二个数大于等于*/
bool NLT(num ,num );

void heapinsert(HEAP &heap,num elem)
{
	int i;
	heap.size ++;
	i = heap.size;           //按照老师课上讲的上溯的方法插值                    
	while (GT(heap.element[i/2],elem ))
	{
		heap.element[i] = heap.element[i/2];
		i/=2;
	}
	heap.element[i] = elem;
}
num heapdelete(HEAP &heap)
{
	num minnum;//根节点，最后返回
	int i;//计数
	num lastelem;//保存最后一个元素
	int count=1;//用于确定下一次循环从左孩子开始还是右孩子开始。
	minnum = heap.element[1];
	lastelem.time = heap.element[heap.size].time;
	lastelem.firstvex = heap.element[heap.size].firstvex;
	lastelem.lastvex = heap.element[heap.size].lastvex;
	heap.element[heap.size].time = 0;
	heap.element[heap.size].firstvex = 0;
	heap.element[heap.size].lastvex  = 0;
	heap.size --;//用老师上课讲的下溯的方法删除
	for (i = 1 ; i * 2 <= heap.size; i = count)
	{
		count *=2 ;
		if (NLT(heap.element[count],heap.element[count +1])&& count < heap.size)
		 count ++;
		if (GT(lastelem,heap.element[count]))
			heap.element[i] = heap.element[count];
		else break;
	}
    heap.element[i] = lastelem;
    return minnum;
}

bool GT(num elem1,num elem2)
{
	if (elem1.time > elem2.time)return 1;
	else return 0;
}
bool NLT(num elem1,num elem2)
{
	if (elem2.time > elem1.time)return 0;
	else return 1;
}

 bool EQU(num elem1,num elem2)
 {
	 if (elem1.time == elem2.time )
	 {
		 return 1;
	 }
	 return 0;

 }
#endif