问答题 设有一大批需实时处理的数据元素组成集合S,实时处理开始后,每隔一极短的时间间隔便收到一个新的数据元素加入S。现要求在每次接收一个新元素之前,找出S中现有的最小元素并将其输出(从S中删除)。试选择或构造一种适当的数据结构并设计一个算法,尽可能高效地完成上述任务(只要求用文字说明算法的基本设计思想)。【同济大学2005三、1(7分)】【中国海洋大学2004七(20分)】
【正确答案】正确答案:这是堆排序问题,先将集合S中的元素建成小堆,并输出堆顶最小元素。再将每隔一极短的时间间隔收到的新数据元素放到堆顶,进行调堆,再输出堆顶元素,如此反复进行。请参考上面第34题堆排序算法。
【答案解析】