最小优先队列实现赫夫曼树 贪心策略

使用 最小优先队列存放要编码的key，和合并之后内部节点，注意最小优先队列，获得最小值时会把最小是删掉，下面是java实现。

package Algorithms;
class MinQueue
  
   >{
	int heapSize;
	T[] heap;
	int capacity;
	public MinQueue(int capaticty)
	{
		this.capacity=capaticty;
		heapSize=0;
		//因为泛型擦除，泛型不能实例化，只能创建Object，然后再强制类型转换为数组
		//这里不能使用new Object 因为没有comparable，要使用直接父类comparable
		heap=(T[])new Comparable[capaticty];
	}
	/**
	 * 最小优先队列的维护
	 */
	public  void heapfy(int i)
	{
		if(i>=heapSize&&i<0)
		{
			System.out.println("要维护的节点错误");
			return ;
		}
		int left=2*i+1;
		int right=2*i+2;
		int min=i;
		//寻找i与其两个孩子的最小值
		if(left
   
    =capacity) { System.out.println("最小优先队列已满！"); return ; } heap[heapSize]=ele; heapSize++; int child=heapSize-1; int parent=(heapSize/2)-1; while(parent>=0&&heap[parent].compareTo(heap[child])>1) { T temp=heap[parent]; heap[parent]=heap[child]; heap[child]=temp; child=parent; parent=(child+1)/2-1; } } public T extractMin() { if(heapSize<=0) { System.out.println("没有元素"); return null; } T min=heap[0]; heapSize--; heap[0]=heap[heapSize]; heap[heapSize]=min; heapfy(0); return min; } } public class HumanCode { public static class Node implements Comparable
    
     { public int freq;//字符出现的频率 public char key; public Node left; public Node right; public Node (int freq,char key,Node left,Node right) { this.freq=freq; this.key=key; this.left=left; this.right=right; } @Override public int compareTo(Node o) { if(this.freq>o.freq) return 1; else if(this.freq==o.freq) return 0; else return -1; } } /** * @param q * 构建哈夫曼树 具有n个关键字要进行n-1次合并 */ public Node huffman(MinQueue
     
       q) { int n=q.heapSize; for(int i=1;i
      
       q=new MinQueue
       
        (6); Node node1=new HumanCode.Node(5, 'f', null, null); Node node2=new HumanCode.Node(9, 'e', null, null); Node node3=new HumanCode.Node(12, 'c', null, null); Node node4=new HumanCode.Node(13, 'b', null, null); Node node5=new HumanCode.Node(16, 'd', null, null); Node node6=new HumanCode.Node(45, 'a', null, null); q.insert(node1); q.insert(node2); q.insert(node3); q.insert(node4); q.insert(node5); q.insert(node6); Node node=hu.huffman(q); hu.huffmanAccess(node,""); } }