最小優先隊列實現赫夫曼樹 貪心策略

最小優先隊列實現赫夫曼樹 貪心策略

使用 最小優先隊列存放要編碼的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;iq=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,"");
	}
}