论文部分内容阅读
中位数求法通常利用排序算法获取,其时间复杂度达到O（n＊ln n）甚至O（n^2）。对于数据流,逐点利用排序法求中位数序列,时间复杂度更高,当数据量很大时,运行极其费时,文中提出利用堆结构获取数据流中位数序列的方法。描述基本思想,分析堆的构造方法,详细介绍算法实现过程。其时间复杂度仅为O（n＊ln n）,较常用的排序算法有较大的改进。最后,通过实验进一步证实该算法的优越性。