最小序列问题

由于工作安排的原因，可能暂时不会再学python了。因此有关python的文章，这可能是最后一篇（目前）。但我会继续更新其他的东西。
这篇关于最小序列的问题。我目前知道的就两种方法，一种就是穷举，这种就是我这种吊丝程序员常用的方法。方法很有效，但遇到数据很大的时候，性能就很差。或者对时间复杂度有要求的话，再使用这种方法就行不通了。我这里使用的是下面一种方法。是通过建堆的方式。这种方式会牺牲一点内存空间。但性能很好。具体的就不说了。 看代码吧

 

# -*- coding: cp936 -*-
#---------------------------------------------
#                                            -
#author  chile                                    -
#version   1.0                                  -
#since                                       -
#date  2014-02-27                                      -
#desc  最小序列                                    -
#                                            -
#                                            -
#                                            -
#---------------------------------------------

def mink(srcArr,mink):
    minArr = initSerial(srcArr,mink) #初始化目标数组
    minArr = buildHeap(minArr) #将目标数组键最大堆
    index = mink
    step = 1;
    while(index < len(srcArr)):
        print '构造步骤 ', step , ': ',minArr 
        if srcArr[index] < minArr[0]: #当前堆与原数组中后面的数比较 
            minArr[0] = srcArr[index] #如果存在比当前堆中小的数，则替换
            minArr = maxHeap(minArr,1,mink) #在重新键最大堆
        index += 1
        step += 1
        
    return minArr

#键最大堆
def buildHeap(minArr):
    heapsize = len(minArr)
    index = heapsize / 2;
    while(index > 0):
        temp = maxHeap(minArr,index,heapsize)
        minArr = temp
        index -= 1
    return minArr

#调整堆大小
def maxHeap(minArr,i, heapsize): 
    largest , left , right = i , 2 * i , 2 * i + 1
    if left <= heapsize and minArr[i - 1] < minArr[left - 1]:
        largest = left
    if right <= heapsize and minArr[largest - 1] < minArr[right - 1]:
        largest = right
    if largest != i:
        temp = minArr[i - 1]
        minArr[i - 1] = minArr[largest - 1]
        minArr[largest - 1] = temp
        maxHeap(minArr,largest,heapsize)
    return minArr
        
def initSerial(srcArr,k):
    minArr = []
    index = 0;
    for val in srcArr:
        if index == k:
            return minArr
        minArr.append(val)
        index += 1
    return minArr

srcArr = [4, 7, 8, 6, 10, 14, 16 ,5, 3, 1, 2]
mixK = 4
print '原序列:  ',srcArr
minArr = mink(srcArr,mixK)
print '最小序列：',minArr