二进制堆排序算法的改进研究

Improvement of Binary Heap Order Algorithm

基于对网络服务质量中队列调度算法的介绍和分析,从队列的优先级角度出发,对经典的二进制堆Heap调度排序算法进行了改进,提出了一种新的Heap+算法,该算法充分利用原算法出队、入队操作数固定的特点,使其在保证硬件实现复杂度低的情况下能够做到出队、入队操作的流水化,从而达到高度的并行性。且具备很高的资源利用率和可扩展性,可用于高速链路上高精度虚拟时间的排序操作。

With introduction and analysis of the queue scheduling algorithm in the network quality of service and in view of queue priority, the modifications on the classical binary heap scheduling algorithm are described, a new Heap＋ algorithm is proposed. The algorithm, by fully utilizing the fixed operand characteristics of the original algorithm in de-queue and en-queue, could achieve pipelining of de-queue and en-queue operations under the condition of ensuring a low hardware complexity, thus realizing high parallelism. This algorithm, with high resource availability, could be applied on the high-speed data link to the ordering operation of high-precision virtual time.