基于四叉堆优先级队列及逆邻接表的改进型Dijkstra 算法

在深入分析传统Ｄｉｊｋｓｔｒａ算法的基础上，提出了利用基于ｋ 叉堆的优先级队列对算法进行改进的思想，并对３ 种可合并堆进行了比较，从理论上证明了四叉堆在ｋ 叉堆中的最优性，设计了基于四叉堆优先级队列及逆邻接表、顾及路段方向阻抗的改进型Ｄｉｊｋｓｔｒａ最短路径算法，将Ｄｉｊｋｓｔｒａ 算法复杂度降为Ｏ（ｎｌｏｇｎ）。针对ＧＩＳ－Ｔ应用系统的动态特征，提出了Ｄｉｊｋｓｔｒａ 算法的逆序计算方法，通过构造逆序最短路径树，使算法更具灵活性和实用性  

最优堆排序算法

本文讨论了堆的若干性质，提出对堆排序算法的改进，改进后的堆排序算法是一个最优排序算法，在最坏情况下需要ｎｌｏｇｎ＋ｎａ３（ｎ）＋Ｏ（ｎ）次元素比较和ｎｌｏｎ＋Ｏ（ｎ）次元素移动。  

一种基于时钟粒度细化的Linux实时化方案

时钟精度直接影响到任务能否被及时响应和调度，作为一个分时系统，Linux的10ms周期性时钟粒度是必要而且合适的．但是实时系统一般都要求微秒级的响应精度，显然Linux的时钟粒度过于粗糙．然而简单地提高时钟频率意味着时钟中断的相应处理过程将占用过多的处理器时间，从而使得整个系统的有效利用率急剧下降．为了改进Linux的实时性能，讨论了基于Linux的实时操作系统RFRTOS中的时钟粒度细化方案．实验结果显示所做改进以不大的代价有效地提高了Linux的时钟精度．  

Linux实时调度方案的设计与实现

作为一个分时系统，Linux的设计目标为提高吞吐率和平均响应时间，因此采取了基于时间片的调度策略，显然这种机制无法保证实时任务得到及时响应和调度．为了改进Linux操作系统的实时性能，探讨了基于Linux的实时操作系统RFRTOS中的实时调度机制．实验验证，所做改进有效地提高了Linux的调度精度，满足了软实时方面的需求．  

立体堆分类算法设计与分析

本文在完全立体二叉树的基础上，提出了立体堆的分类方法，并对它的算法实现进行设计与分析，得出了立体堆分类方法在最坏情况下的时间复杂性，从而减小了堆分类方法的时间复杂性的常数因子。  

基于业务的多优先级队列区别服务方案

缓冲队列的管理和调度是有关互连网服务质量的重要话题。鉴于时延是QoS(QualityofService)的一个重要指标,论文提出并详细讨论了一种基于EDF(EarliestDeadlineFirst)的优先级队列PQBEDF(priorityqueuebasedonEDF),针对不同的业务类型采用各自的PQBEDF,这样可以使得“区别”更加合理,且便于各队列采用不同的控制策略。配以异步时分机制,可以对每一类业务的信元保证一个最小的服务速率。  

Windows下堆内存管理机制研究

堆是用来存储动态数据的内存区域。通过堆函数，可以在进程的地址空间里创建私有堆，继而可以通过系统提供的一系列函数来管理堆中的内存。首先分析了堆的基本结构。然后通过对Windows堆中内存块的分配和释放进行深入分析。详细阐述堆内存的管理机制。  

基于四叉堆优先级队列及逆邻接表的改进型Dijkstra算法

在深入分析传统Ｄｉｊｋｓｔｒａ算法的基础上，提出了利用基于ｋ叉堆的优先级队列对算法进行改进的思想，并对３种可合并替进行了比较，从理论上证明了四叉堆在ｋ叉堆中的最优性，设计了基于四叉堆优先级队列及逆领接表，顾及路段方向阻抗的改进型Ｄｉｊｋｓｔｒａ最短径算法，将Ｄｉｊｓｔｒａ算法复杂度降为Ｏ（ｎｌｏｇｎ）。  

两种新的缓冲区溢出攻击原理及防范

论文主要分析了两种新的缓冲区溢出攻击形式所利用的原理，即：格式化串和HEAP／BSS。并在此基础上提出了相应的防范策略。  

Algorithms for a Class of Isotonic Regression Problems

The isotonic regression problem has applications in statistics, operations research, and image processing. In this paper a general framework for the isotonic regression algorithm is proposed. Under this framework, we discuss the isotonic regression problem in the case where the directed graph specifying the order restriction is a directed tree with n vertices. A new algorithm is presented for this case, which can be regarded as a generalization of the PAV algorithm of Ayer et al. Using a simple tree structure such as the binomial heap, the algorithm can be implemented in O(n log n) time, improving the previously best known O(n ² ) time algorithm. We also present linear time algorithms for special cases where the directed graph is a path or a star. Received September 2, 1997; revised January 2, 1998, and February 16, 1998.