minheap.h

霍夫曼编码对于不同权值的字母进行编码,根据优先级输出.

#ifndef MINHEAP_H_
#define MINHEAP_H_

#include <iostream>
#include "TreeNode.h"

using namespace::std;

const size_t DEFAULT_CAP = 20;    //default capacity

class MinHeap
{
public:
	MinHeap() : m_count(0), m_capacity(DEFAULT_CAP)
	{
		m_pcontainer = new TreeNode[m_capacity];
	}

	MinHeap( size_t cap) : m_count(0), m_capacity(cap)
	{
		m_capacity = (cap > DEFAULT_CAP) ? cap : DEFAULT_CAP;
		m_pcontainer = new TreeNode[m_capacity];
	}

	MinHeap( int* ary, size_t n)
	{
		m_capacity = n;
		m_pcontainer = new TreeNode[m_capacity];

		for(int i = 0; i < n; i++) {
			m_pcontainer[i].data = ary[i];
		}

		m_count = 8;

		
	}

	~MinHeap()
	{
		delete[] m_pcontainer;
	}

	size_t size() const { return m_count; }

	size_t capacity() const { return m_capacity; }

	bool IsEmpty() const { return m_count == 0; }
	
	bool IsFull() const { return  m_capacity == m_count; }
	
	void MakeEmpty() { m_count = 0; }
	
	bool Insert( const TreeNode &x )
	{
		if( m_count == m_capacity ) {
			cout << "Heap Is Full!\n" <<endl;
			return false;
		} else {
			m_pcontainer[m_count] = x;
			m_count++;
			FilterUp(m_count - 1);
			return true;
		}    
	}

	TreeNode* RemoveMin()
	{
		if( m_count == 0) {
			cout << "Heap Is Empty!\n" << endl;
			return NULL;
		} else {
			TreeNode *x = new TreeNode(m_pcontainer[0].data);
			x->left = m_pcontainer[0].left;
			x->right = m_pcontainer[0].right;


			m_pcontainer[0] = m_pcontainer[--m_count];
			FilterDown(0, m_count - 1);
			//cout<<x<<endl;
			return x;
		}    
	}

protected:
	void FilterDown( int start, int end )
	{
		if(end < 0)
			return;
		int rc = m_pcontainer[start].data;

		for(int j = 2 * start + 1; j <= end; j = 2 * j + 1)
		{
			if(j < end && m_pcontainer[j].data > m_pcontainer[j+1].data) {
				j++;
			}

			if (rc <= m_pcontainer[j].data )
				break;
			m_pcontainer[start].data = m_pcontainer[j].data;
			start = j;
		}

		m_pcontainer[start].data = rc;
	}

	void FilterUp( int istart )
	{
		int j = istart;
		int i =(j-1)/2;
		int temp = m_pcontainer[j].data;

		while( j > 0 ) {
	
			if( m_pcontainer[i].data > temp ) {
				m_pcontainer[j].data = m_pcontainer[i].data;
				j = i;
				i = (j - 1)/2;
			} else {
				break;
			}
		}

		m_pcontainer[j].data = temp;    
   }

private:
	int m_count;              //number of contents
	int m_capacity;          //capacity of container
	TreeNode * m_pcontainer;      //container
};

 

#endif /*MINHEAP_H_*/