minheap.h

常用算法与数据结构原代码

// file MinHeap.h
#ifndef MinHeap_
#define MinHeap_

#include <stdlib.h>
#include <iostream.h>
#include "xcept.h"

template<class T>
class MinHeap 
{
public:
	MinHeap(int MinHeapSize = 10);
	~MinHeap() 
	{
		delete [] heap;
	}
	int Size() const 
	{
		return CurrentSize;
	}
	T Min() 
	{
		if (CurrentSize == 0)
			throw OutOfBounds();
		return heap[1];
	}
	MinHeap<T>& Insert(const T& x);
	MinHeap<T>& DeleteMin(T& x);
	void Initialize(T a[], int size, int ArraySize);
	void Deactivate() 
	{
		heap = 0;
	}
	void Output() const;
private:
	int CurrentSize, MaxSize;
	T *heap; // element array
};

template<class T>
MinHeap<T>::MinHeap(int MinHeapSize)
{// Min heap constructor.
	MaxSize = MinHeapSize;
	heap = new T[MaxSize+1];
	CurrentSize = 0;
}

template<class T>
MinHeap<T>& MinHeap<T>::Insert(const T& x)
{// Insert x into the min heap.
	if (CurrentSize == MaxSize)
		throw NoMem(); // no space
	
	// find place for x
	// i starts at new leaf and moves up tree
	int i = ++CurrentSize;
	while (i != 1 && x < heap[i/2]) 
	{
		// cannot put x in heap[i]
		heap[i] = heap[i/2]; // move element down
		i /= 2; // move to parent
	}
	heap[i] = x;
	
	return *this;
}

template<class T>
MinHeap<T>& MinHeap<T>::DeleteMin(T& x)
{// Set x to min element and delete
	// min element from heap.
	// check if heap is empty
	if (CurrentSize == 0)
		throw OutOfBounds(); // empty
	
	x = heap[1]; // min element
	
	// restructure heap
	T y = heap[CurrentSize--]; // last element
	
	// find place for y starting at root
	int i = 1,  // current node of heap
		ci = 2; // child of i
	while (ci <= CurrentSize) 
	{// find place to put y
		// heap[ci] should be smaller child of i
		if (ci < CurrentSize &&	heap[ci] > heap[ci+1])
			ci++;
		
		// can we put y in heap[i]?
		if (y <= heap[ci]) 
			break;  // yes
		
		// no
		heap[i] = heap[ci]; // move child up
		i = ci;  // move down a level
		ci *= 2;
	}
	heap[i] = y;
	
	return *this;
}

template<class T>
void MinHeap<T>::Initialize(T a[], int size, int ArraySize)
{// Initialize min heap to array a.
	delete [] heap;
	heap = a;
	CurrentSize = size;
	MaxSize = ArraySize;
	
	// make into a min heap
	for (int i = CurrentSize/2; i >= 1; i--) 
	{
		T y = heap[i]; // root of subtree
		
		// find place to put y
		int c = 2*i; // parent of c is target
		// location for y
		while (c <= CurrentSize) 
		{
			// make c point to smaller sibling
			if (c < CurrentSize && heap[c] > heap[c+1]) 
				c++;
			
			// can we put y in heap[c/2]?
			if (y <= heap[c]) 
				break;  // yes
			
			// no
			heap[c/2] = heap[c]; // move heap[c] up
			c *= 2;              // move c down a level
		}
		heap[c/2] = y;
	}
}

template<class T>
void MinHeap<T>::Output() const
{
	cout << "The " << CurrentSize
        << " elements are"<< endl;
	for (int i = 1; i <= CurrentSize; i++)
		cout << heap[i] << ' ';
	cout << endl;
}

#endif