堆排序

#对于一个含有N个元素的基于堆的优先队列，插入元素操作只需要不超过（lg(N)+1）次比较，删除最大元素的操作不超过
#2lg(N)次比较。
class Dui:
    def __init__(self):
        self.pq = []#基于堆的完全二叉树
        self.N = 0#存储于pq[1,...N]中，pq[0]没有使用

    def __init__(self,num):
        self.pq = [0] * (num+1)
        self.N = 0

    def isEmpty(self):
        return self.N==0

    def size(self):
        return self.N

    def insert(self, v):#向堆中插入元素
        self.N = self.N + 1
        self.pq[self.N] = v
        k = self.N
        while k > 1 and self.pq[int(k/2)] < self.pq[k]:#元素上升
            self.pq[int(k/2)],self.pq[k] = self.pq[k], self.pq[int(k/2)]
            k = int(k/2)

    def delMax(self):
        maxNumber = self.pq[1]#从根节点得到最大元素
        self.pq[1],self.pq[self.N] = self.pq[self.N],self.pq[1]#将其和最后一个节点交换
        self.N = self.N - 1#堆的元素减少一个
        self.pq[self.N+1] = None#防止对象游离
        k = 1
        while 2*k <= self.N:#元素下沉
            j = 2*k
            if j<self.N and self.pq[j]<self.pq[j+1]:
                j = j + 1
            if self.pq[k] >= self.pq[j]:
                break
            self.pq[k],self.pq[j] = self.pq[j],self.pq[k]
            k = j
        return maxNumber

    def getElements(self):#获得堆结构的元素
        return self.pq[1:self.N+1]

堆排序

原文：http://my.oschina.net/stevenKelly/blog/390520