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 #include "Vector/Vector.h" //借助多重继承机制,基于向量 0010 #include "PQ/PQ.h" //按照优先级队列ADT实现的 0011 template <typename T> struct PQ_ComplHeap : public PQ<T>, public Vector<T> { //完全二叉堆 0012 PQ_ComplHeap() { } //默认构造 0013 PQ_ComplHeap ( T* A, Rank n ) { copyFrom ( A, 0, n ); heapify ( _elem, n ); } //批量构造 0014 void insert ( T ); //按照比较器确定的优先级次序,插入词条 0015 T getMax(); //读取优先级最高的词条 0016 T delMax(); //删除优先级最高的词条 0017 }; //PQ_ComplHeap 0018 template <typename T> void heapify ( T* A, Rank n ); //Floyd建堆算法 0019 template <typename T> Rank percolateDown ( T* A, Rank n, Rank i ); //下滤 0020 template <typename T> Rank percolateUp ( T* A, Rank i ); //上滤 0021