十二、堆.pptVIP

十二、堆 堆的定义 堆的定义 堆是结点间具有层次次序关系的完全二叉树。其定义如下： 有一个关键码的集合K = {k0，k1，k2，…，kn-1}，相应的元素按 完全二叉树存放于一个一维数组，并满足 ki≤k2i+1 且ki≤k2i+2 (ki≥k2i+1 且ki≥k2i+2 ) (i = 0, 1, …, ︱(n-1) /」) 称这个集合为最小堆(或最大堆)。 最小堆 最大堆 堆类 堆类说明 templateclass 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 HeapT H); ～Heap(void); 堆类(续) (续上页) 堆类说明 // 重载运算符：“=”，“[ ]”，“T*” HeapT operator = (const HeapT 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); }; 堆元素的插入与删除 堆元素的插入 总是添加在表尾，然后再调整成堆 堆元素的删除 删除总是在根处，拿根与表尾交换，实际是删除表尾 堆元素的插入 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算法 templateT void HeapT∷Insert(const T item) { if(heapsize = = maxheapsize) // 堆满出错 error(“Heap full”); // 将元素插入堆尾 hlist[heapsize] = item; // 用Filterup调整堆 FilterUp(heapsize); // 堆大小加1 heapsize + +; } 从上至