《算法导论》笔记－－优先级队列

 

　　优先级队列也是一种基础的数据结构，应用非常广泛，并且经常作为其它算法的一部分出现。优先级队列一般分最大优先级队列和最小优先级队列。这两种优先级队列只是为了适应不同场合的需要而进行区分实现，在算法上来讲没有什么本质的不同。因此下面只讲最大优先级队列，所记内容都同时对称地适用于最小优先级队列。

　　最大优先级队列，是这样的一种队列结构，它的内部存放着一系列的元素，每个元素都对应着一个最优级，最大优先级队列不管各元素的入队顺序，在出队时，总是对应优先级最大的元素出队。比如对许多等待运行的进程来讲，进程调度器每次都取出一个优先级最高的进程执行一段时间，再取下一个优先级最高的进程，如此往复，就需要用到像最大优先级队列这样的结构。并且，最大优先级队列一般还会提供改变队列内元素优先级的操作。

最大优先级队列一般用二叉树来实现。因为考虑到，对于最大优先级队列来讲，我们关心的只是最大值，因此，这时的二叉树只需要具备下面这个性质，那么就可以实现了：

　　性质A：总是让二叉树中的每一个节点的key（也就是优先级）值比该节点的子节点的key值大。

　　保持性质A就可以在每次出队操作时，直接取根节点得到最大优先级的元素。然后再进行树结构的调整，使得取出根节点之后，二叉树仍然保持性质A。

　　这样的二叉树可以保证，每个入队和出队的操作都在O(h)的时间内完成（h是树的高度）。入队和出队的操作，就不详细记述了（《算法导论》上讲得很清楚，网上也能找到一大堆的资料）。关键思想都是比较子树的父节点、左子节点、右子节点三个的值，然后将最大的调整到父节点，再对于与父节点进行交换的节点位置递归进行上述比较，最多的比较次数是沿根到叶的最大路径长（也就是树高h）。

　　另外，考虑到这个树要保证的性质只有性质A，那么可以让这棵二叉树总是保持为完全二叉树（且不破坏性质A），这样树高就会是lgn，那么入队和出队操作的时间复杂度就是O(lgn)。这就比较理想了。

　　对于一棵完全二叉树，我们可以用数组（而不是链表）方式来实现。因为对于数组实现的完全二叉树，index为i的节点，它的父节点的index是i/2，左子节点的index是i*2，右子节点的index是i*2+1。乘2和除2都是可以通过位移来实现的，效率上很好。而且通过保存元素个数，可以O(1)时间只找到处于树的最未的那个元素。用数组来实现还有一个好处，就是不需要在数据结构中再实现对父、子节点的指针存储，这样也省下了不少空间。这些特点都非常适合（也很好地改善了）优先级队列的实现。

 

 

以下是python代码实现：

class QueueElement:
    """
    Private class only for class QHeap. Suppling as a device to cobmine
    key and object together.
    """
    def __init__(self, obj, prio):
        self.key = prio
        self.obj = obj
    

class QHeap: # max heap
    """
    Private class
    Implement the basic data structure for Priority Queue.
    """
    def __init__(self, compare):
        self.HeapAry = [0]
        # method given by subclass. for config whether be a maxqueue or a minqueue.
        self.com = compare 
    def EnQueue(self, obj, priority):        
        self.HeapAry.append(QueueElement(obj, priority))
        i = self.QueueLen()
        while (i > 1) and self.com(self.HeapAry[i/2].key, self.HeapAry[i].key):
            self.HeapAry[i/2] ,self.HeapAry[i] = \
                self.HeapAry[i] ,self.HeapAry[i/2]
            i = i/2
        
    def __MakeHeapify(self, i):        
        if i > self.QueueLen()/2:
            return
        max_idx = i
        # find out the maximun(or minmun, judged by self.com method) one in 
        # parent,left and right node. Identify it be max_idx
        if self.com(self.HeapAry[max_idx].key, self.HeapAry[i*2].key):
            max_idx = i*2
        if i*2+1 <= self.QueueLen() and self.com(self.HeapAry[max_idx].key, self.HeapAry[i*2 + 1].key):
            max_idx = i*2 + 1
        # if the max_idx is not parent, exchange parent and max_idx element.
        if max_idx != i:
            self.HeapAry[max_idx] ,self.HeapAry[i] = \
                self.HeapAry[i] ,self.HeapAry[max_idx]
            self.__MakeHeapify(i*2)
    
    def DeQueue(self):
        head = self.HeapAry[1]
        last = self.HeapAry.pop()
        if (self.QueueLen() >= 1):
            self.HeapAry[1] = last
            self.__MakeHeapify(1)   
        return head.obj     
        
    def QueueLen(self):
        return len(self.HeapAry) - 1
    def Empty(self):
        return self.QueueLen() == 0
    
class MaxPrioQueue(QHeap):
    """
    Maximun priority queue.
    """
    def __init__(self):
        # max queue use x < y to judge the change node configration.
        self.com = lambda x, y: x < y
        self.HeapAry = []

class MinPrioQueue(QHeap):
    """
    Minmun priority queue.
    """
    def __init__(self):
        # max queue use x > y to judge the change node configration.
        self.com = lambda x, y: x > y
        self.HeapAry = []    

#-----------------------------------------------------------------
# for test only.

if __name__ == '__main__':
    h = MaxPrioQueue()
    chars = ['L', 'i', 'Y', 'i', 'W', 'e', 'n']
    keys  = [ 8 ,  4 ,  6 ,  3 ,  10,  9 ,  5 ]
    for i in range(0, len(chars)):
        h.EnQueue(chars[i], keys[i])
    result = []
    while not h.Empty():
        result.append(h.DeQueue())        
    print "length of result is %d:" % len(result)
    print "".join(result)
    
    h = MinPrioQueue()
    for i in range(0, len(chars)):
        h.EnQueue(chars[i], keys[i])
    result = []
    while not h.Empty():
        result.append(h.DeQueue())        
    print "length of result is %d:" % len(result)
    print "".join(result)