maxheap.h

贪婪算法合集,包括二分覆盖,单源最短路径,拓扑排序,机器调度问题

//最大堆的类定义，CurrentSize是私有成员，代表目前堆中元素的个数，MaxSize是堆的最大容量，heap是存储堆元素的数组，缺省大小为10个元素
#ifndef MaxHeap_
#define MaxHeap_

#include<cstdlib>
#include<iostream>
#include"xcept.h"
using namespace std;

template<class T>
class MaxHeap {
   public:
      MaxHeap(int MaxHeapSize = 10);
      ~MaxHeap() {delete [] heap;}
      int Size() const {return CurrentSize;}
	  bool IsEmpty()const{return CurrentSize==0;}
	  bool IsFull()const{return CurrentSize==MaxSize;}
	  MaxHeap<T>& ChangeMax(const T& x);//根据练习8而来
      T Max() {if (CurrentSize == 0) throw OutOfBounds();return heap[1];}
      MaxHeap<T>& Insert(const T& x);
      MaxHeap<T>& DeleteMax(T& x);
	  MaxHeap<T>& DeleteMax2(T& x);//书中习题重新设计的Delete,也就是除掉最后一个元素后，先移好了再插入它
      void Initialize(T a[], int size, int ArraySize);
      void Deactivate() {heap = 0;}//在初始化函数中，将整个数组元素放入类中。这样一来，当超出最大堆的范围而又仍想访问数组a中
	                      //的元素时，会产生问题，为避免这个问题，加入这个函数，通过使用该函数，可以防止调用堆的析构函数时将a删除
      void Output() const;
   private:
      int CurrentSize, MaxSize;
      T *heap;  //元素数组
};

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

template<class T>
MaxHeap<T>& MaxHeap<T>::Insert(const T& x)
{//把x插入到最大堆中
   if (CurrentSize == MaxSize)
      throw NoMem(); //没空间了

   //为x寻找应该插入的位置
   //i从新的叶节点开始，并沿着树上升
   int i = ++CurrentSize;//+1即为新的位置
   while (i != 1 && x > heap[i/2])//注意，根节点编号为1，另外上升到父节点，根据完全二叉树定义，应该是i=i/2;
   {
      //此，循环表示x值比较大，寻找适当位置
      heap[i] = heap[i/2]; //将这个小的父节点heap[i/2]值赋给其孩子
      i /= 2;              //索引i沿着树上升，因为跟父节点的关系为/2，所以这里i/=2
      }

   heap[i] = x;//最后，终于找到此位置，插入x
   return *this;
}

template<class T>
MaxHeap<T>& MaxHeap<T>::DeleteMax(T& x)
{//将最大元素存入x，并从堆中删除它，重新组合堆
   //检查堆是否为空
   if (CurrentSize == 0) throw OutOfBounds();

   x = heap[1]; //最大就是第一个值了

   //重构堆
   T y = heap[CurrentSize--]; //取出最后一个元素来，同时CurrentSize-1

   //从根开始为y寻找合适的位置
   int i = 1,  //堆的当前节点
       ci = 2; //i的孩子
   while (ci <= CurrentSize) {
      //ci初始化为2，以下这个if寻找左右孩子中较大的一个。
      if (ci < CurrentSize && heap[ci] < heap[ci+1]) ci++;

      //之后，验证y是否比这个最大的还大，如果大，则break，while体外插入y
      if (y >= heap[ci]) break;   // yes

      //否则
      heap[i] = heap[ci]; //移动这个较大的孩子到删除的根节点
      i = ci;             //ci赋给i，也就是下移一层，以便继续作比较
      ci *= 2;            //当然ci也要下移一层了，ci*2，也就是到了这个较大节点的左孩子，
      }
   heap[i] = y;

   return *this;
}

template<class T>
MaxHeap<T>& MaxHeap<T>::ChangeMax(const T& x)
{//改变最大元素为x
   //看看是否为空先
   if (CurrentSize == 0)
      throw OutOfBounds(); // empty

   //重构堆
   T y = x;

   // find place for y starting at root
   int i = 1,  //当前
       ci = 2; //i的孩子
   while (ci <= CurrentSize) {
      //仍然是heap[ci]应该是较大一个
      if (ci < CurrentSize &&
          heap[ci] < heap[ci+1]) ci++;

      //我们能放入y到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 MaxHeap<T>::Initialize(T a[], int size,int ArraySize)
{//把最大堆初始化为数组a
   delete [] heap;//释放先
   heap = a;
   CurrentSize = size;
   MaxSize = ArraySize;

   //产生一个最大堆
   for (int i = CurrentSize/2; i >= 1; i--)//按照算法，从n/2开始
   {
      T y = heap[i]; //取得子树的根

      //寻找放置y的位置
      int c = 2*i; //c为位置i的左孩子，它的父节点是y的目标位置
      while (c <= CurrentSize)
	  {
         //定位i的左右孩子中较大的一个为c
         if (c < CurrentSize && heap[c] < heap[c+1]) c++;

         //如果y大于这个较大的，则可见y能放入c/2，所以break，在while外面插入y
         if (y >= heap[c]) break;  // yes

         //否则
         heap[c/2] = heap[c]; // 将这个较大孩子上移
         c *= 2; //下移一层，以便i继续与下面的比较
         }
      heap[c/2] = y;
      }
}

template<class T>

MaxHeap<T>& MaxHeap<T>::DeleteMax2(T& x)

{
	if (CurrentSize == 0)
		throw OutOfBounds();// empty
	
	x = heap[1]; //最大元素

   //重构堆
   T y = heap[CurrentSize--]; //最后一个元素

   // first propagate vacancy to a leaf

   int i = 1,  // current node of heap
       ci = 2; // child of i

   while (ci <= CurrentSize)
   {
      // heap[ci] 应该是 大孩子of i

      if (ci < CurrentSize && heap[ci] < heap[ci+1]) ci++;
      //将大孩子move到父节点i
      heap[i] = heap[ci]; // move child up
      i = ci;             // 下移一层
      ci *= 2;
   }
   i = ci/2;
   // vacancy at heap[i], start from here
   // and insert y
   while (i != 1 && y > heap[i/2])
   {
	   // cannot put y in heap[i]
      heap[i] = heap[i/2]; // move element down
      i /= 2;              // move to parent
   }
   heap[i] = y;

   return *this;
}

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

#endif