main.cpp

huffman树的实现。对于压缩有很好的用途。 高效且简单

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int left[100],right[100],key[100],root,length;
int heap[100],hs;

void build();
void sink(int p);
int deletemin();
void join();
void newnode(int p);

int main()
{
	srand(unsigned(time(NULL)));
	int i;
	for (i=1;i<=5;i++) {
		heap[i]=i;
		key[i]=rand()%20;
	}
	hs=length=5;
	build();
	join();
	return 0;
}

void sink(int p)
{
	int q=p<<1,a=heap[p];
	while (q<=hs)
	{
		if (q<hs&&key[heap[q]]>key[heap[q+1]]) q++;
		if (key[a]<key[heap[q]]) break;
		heap[p]=heap[q];
		p=q;
		q=p<<1;
	}
	heap[p]=a;
}

void build()
{
	for (int i=hs/2;i>0;i--) sink(i);
}
int deletemin()
{
	int a=heap[1];
	heap[1]=heap[hs--];
	sink(1);
	return a;
}
void join()
{
	int p;
	while (hs>1)
	{
		p=key[heap[2]]<key[heap[3]]?2:3;
		newnode(p);
		deletemin();
		sink(p);
	}
}
void newnode(int p)
{
	length++;
	key[length]=key[heap[1]]+key[heap[p]];
	right[length]=heap[1];left[length]=heap[p];
	heap[p]=length;
}