优先队列上的快速并行算法

Quick Parallel Algorithm for Priority Queue

利用上浮路径、下沉路径的概念，采用二分查找定位技术，提出了堆上并行插入删除的新算法；最坏情况下使得原有并行插入算法的ｌｏｇＮ次加锁操作降低到ｌｏｇｌｏｇＮ＋θ（１）次；原有并行删除算法的２ｌｏｇＮ次加锁操作降低到ｌｏｇＮ＋ｌｏｇｌｏｇＮ＋θ（１）次，其中Ｎ为堆中元素的个数．最大限度地扩展了堆上操作的并行度．

A new parallel insertion and deletion algorithm for heap is presented in this paper byusing ascending path, descending path, and binary search method. At the worst case, the logN lock operations of old parallel insertion algorithm is reduced to loglogN+θ(1), the 2logN lock operations of old parallel deletion algorithm is reduced to logN+loglogN+θ(1), there N is the number of element of heap. The parallelism of operation in heap is expanded into a maximum.