0001 /****************************************************************************************** 0002 * Data Structures in C++ 0003 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3 0004 * Junhui DENG, deng@tsinghua.edu.cn 0005 * Computer Science & Technology, Tsinghua University 0006 * Copyright (c) 2003-2019. All rights reserved. 0007 ******************************************************************************************/ 0008 0009 //对向量中的第i个词条实施上滤操作,i < _size 0010 template <typename T> Rank percolateUp ( T* A, Rank i ) { 0011 while ( 0 < i ) { //在抵达堆顶之前,反复地 0012 Rank j = Parent ( i ); //考查[i]之父亲[j] 0013 if ( lt ( A[i], A[j] ) ) break; //一旦父子顺序,上滤旋即完成;否则 0014 swap ( A[i], A[j] ); i = j; //父子换位,并继续考查上一层 0015 } //while 0016 return i; //返回上滤最终抵达的位置 0017 }