12.4  小结

(1) ADT表支持面向值的操作，例如：检索有关John Smith的所有信息。

(2) 表的基于数组和基于引用的线性实现只适用于特定的情形，如表小，或对于某些操作，表的线性实现可满足要求；此时，线性实现的简单性是一个优势。不过，表的线性实现不适用于通用、可重用的类。

(3) 二叉查找树是基于引用的非线性实现。ADT表的基于二叉查找树的实现汲取了两种线性实现的优点。基于引用的实现允许表动态增长，并可以只通过几个引用更改就完成数据的插入和删除。另外，在查找包含特定值的项时，二叉查找树允许使用类似于二叉查找的算法。在很多应用程序中，这些特性使非线性的实现远优于线性实现。

(4) 优先队列是ADT表的变体，其操作可以检索和删除包含最大优先级值的项。

(5) 堆使用完全二叉树的基于数组的表示。若知道每次排序的最大项数，则堆是优先队列的一个很好的实现。

(6) 与归并排序一样，堆排序在最坏情况和平均情况下都有较好的表现，但在平均情况下，这两种算法都不如快速排序。堆排序要比归并排序好些，因为它不需要辅助数组。