十二、堆 堆的定义

堆是结点间具有层次次序关系的完全二叉树。其定义如下： 有一个关键码的集合K = {k0，k1，k2，…，kn-1}，相应的元素按 堆的定义 堆是结点间具有层次次序关系的完全二叉树。其定义如下： 有一个关键码的集合K = {k0，k1，k2，…，kn-1}，相应的元素按 完全二叉树存放于一个一维数组，并满足 ki≤k2i+1 且ki≤k2i+2 (ki≥k2i+1 且ki≥k2i+2 ) (i = 0, 1, …, ︱(n-1) /」) 称这个集合为最小堆(或最大堆)。 最小堆 最大堆 09 87 17 78 53 65 45 87 45 65 09 31 78 23 53 31 17 23

堆类 堆类说明 template<class T> class Heap { private: T*hlist; int inArray; int maxheapsize; // 堆中可存放的元素的最大个数 int heapsize; // 最后一个元素位置 void error(char errmsg[ ]); void FilterDown(int i); // 向下调整 void FilterUp(inr i); // 向上调整 public: Heap(int maxsize); // 建立空堆 Heap(T arr[ ], int n); // 对数组arr调整成堆 Heap(const Heap<T>& H); ～Heap(void);

堆类(续) (续上页) 堆类说明 // 重载运算符：“=”，“[ ]”，“T*” Heap<T>& operator = (const Heap<T>& rhs); const T& operator[ ] (int i); // 有关的表函数 int ListSize(void) const; int ListEmpty(void) const; int ListFull(void) const; void Insert(const T& item); T Delete(void); void ClearList(void); };

删除总是在根处，拿根与表尾交换，实际是删除表尾 堆元素的插入与删除 堆元素的插入 总是添加在表尾，然后再调整成堆 堆元素的删除 删除总是在根处，拿根与表尾交换，实际是删除表尾 10 10 40 30 25 30 45 25 45 40 25 25 15 30 30 15 × 40 10 40 10

堆元素的插入 FilterUp算法 void Heap <T>∷FileterUp(int i) { int currentpos, parentpos; // 前者为遍历双亲路径上结点的下标，后者为双亲 T target; // target为hlist[i]的值 currentpos = i; parentpos = (i－1)/2; target = hlist[i]; while (currentpos ! = 0) // 沿双亲路径搜索 if (hlist[parentpos]<= target) break; // 满足堆条件，退出遍历 else { hlist[currrentpos] = hlist[parentpos]; // 交换，双亲值下移 currentpos = parentpos; parentpos = (current －1)/2;} } hlist[currentpos] = target; // 将插入值赋入确定的位置

堆元素的插入(续) Insert算法 template<T> void Heap<T>∷Insert(const T& item) { if(heapsize = = maxheapsize) // 堆满出错 error(“Heap full”); // 将元素插入堆尾 hlist[heapsize] = item; // 用Filterup调整堆 FilterUp(heapsize); // 堆大小加1 heapsize + +; }

从上至下调整堆 Filter Down算法 template<T> void Heap<T>∷FilterDown(int i) { int currentpos, childpos; T target; currentpos = i; target = hlist[i]; childpos = 2*i + 1; while (childpos < heapsize) // 检查表是否结束 if ((childpos+1<heapsize)&& (hlist[childpos+1]<=hlist[childpos])) childpos = childpos+1; // 取较小的孩子

从上至下调整堆(续) Filter Down算法 if (target<=hlist[childpos] // 已是较小的孩子结点下标 break; else { hlist[currentpos] = hlist[childpos]; currentpos = childpos; childpos = 2*currentpos + 1; // 计算新的孩子结点下标 } hlist[currentpos] = target;

堆元素的删除