优先队列

概念

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。

优先队列的实现

通常采用堆数据结构来实现。

堆的定义

堆其实就是一棵完全二叉树（若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边），
定义为：具有n个元素的序列（h1,h2,…hn），当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,…,n/2)时称之为堆

堆排序

import random
import time
class MaxHeap(object):
    def __init__(self):
        self._data = []
        self._count = len(self._data)
    def size(self):
        return self._count
    def isEmpty(self):
        return self._count == 0
    def add(self, item):
        # 插入元素入堆
        self._data.append(item)
        self._count += 1
        self._shiftup(self._count-1)     #堆的序号从0开始
    def pop(self):
        # 出堆
        if self._count > 0:
            ret = self._data[0]
            self._data[0] = self._data[self._count-1]  #移除堆的最顶的元素
            self._count -= 1 
            self._shiftDown(0)    #对移除之后的堆进行排序，使之成为最大堆
            return ret
    def _shiftup(self, index):
        # 上移self._data[index]，以使它不大于父节点
        parent = (index-1)>>1
        while index > 0 and self._data[parent] < self._data[index]:
            # swap
            self._data[parent], self._data[index] = self._data[index], self._data[parent]
            index = parent
            parent = (index-1)>>1
    def _shiftDown(self, index):
        # 上移self._data[index]，以使它不小于子节点
        j = (index << 1) + 1
        while j < self._count :
            # 有子节点
            if j+1 < self._count and self._data[j+1] > self._data[j]:
                # 有右子节点，并且右子节点较大
                j += 1
            if self._data[index] >= self._data[j]:
                # 堆的索引位置已经大于两个子节点，不需要交换了
                break
            self._data[index], self._data[j] = self._data[j], self._data[index]
            index = j
            j = (index << 1) + 1
    def MaxHeap1(self,alist,n):  #n表示alist的长度
        self._data=n*[0]
        for i in range(0,n):
            self._data[i]=alist[i]
        self._count=n
        i=(self._count-1)>>2
        while i>=0:
            self._shiftDown(i)
            i-=1
#通过将数组的数一个一个添加到堆中然后在移出堆的操作实现逆序
def Heapsort1(alist):
    maxheap=MaxHeap()
    for i in range(0,len(alist)):
        maxheap.add(alist[i])
    i=maxheap._count-1
    while i>=0:
        alist[i]=maxheap.pop()
        i-=1
#通过开辟一个与数组同长度的堆，然后赋值->shitfdown使得成为最大堆，最后移出堆操作实现逆序
def Heapsort2(alist):
    #开辟新空间maxheap
    maxheap=MaxHeap()
    maxheap.MaxHeap1(alist,len(alist))
    i=len(alist)-1
    while i>=0:
        alist[i]=maxheap.pop()
        i-=1
#直接对alist逆排序，不创建堆空间
def Heapsort3(alist):
    #对数组heapify
    i=(len(alist)-1)>>1
    while i>=0:
        shiftdown(alist,len(alist),i)
        i-=1
    #对数组进行逆序
    k=len(alist)-1
    while k>0:
        #交换
        alist[k],alist[0]=alist[0],alist[k]
        shiftdown(alist,k,0)
        k-=1
def shiftdown(alist,n,k):
    while 2*k+1<n:   #当左孩子没有越界
        j=2*k+1
        if j+1<n and alist[j+1]>alist[j]:
            j+=1
        if alist[k]>=alist[j]:
            break
        alist[k],alist[j]=alist[j],alist[k]
        k=j
if __name__ == '__main__':
    alist=random.sample(range(0,10000),10000)
    start=time.clock()
    Heapsort3(alist)
    end=time.clock()
    print(end-start)