python 利用堆解决K个有序数列排序问题

# k个有序数组合并成一个有序数组，总数量为n

使用堆排序可以将时间复杂度缩减到O(nlogk),当k较大时会比较有优势，但是我这个代码明显不优美高效，有待改进

class Heap():
    max_heaps = []
    min_heaps = []

    #初始化最大堆
    def add_maxheap(self,list):
        self.max_heaps = list.copy()
        for i in range(len(self.max_heaps)):
            if i ==0:
                continue

            while i>0:
                j = (i-1)//2
                k = (i-2)//2
                if i%2!=0 and self.max_heaps[i]>self.max_heaps[j]:
                    n = self.max_heaps[i]
                    self.max_heaps[i] = self.max_heaps[j]
                    self.max_heaps[j] = n
                    i = j
                    continue
                if i%2==0 and self.max_heaps[i]>self.max_heaps[k]:
                    n = self.max_heaps[i]
                    self.max_heaps[i] = self.max_heaps[k]
                    self.max_heaps[k] = n
                    i = k
                    continue
                break


    # 初始化最小堆
    def add_minheap(self,list):
        self.min_heaps = list.copy()
        for i in range(len(self.min_heaps)):
            if i ==0:
                continue

            while i>0:
                j = (i-1)//2
                k = (i-2)//2
                if i%2!=0 and self.min_heaps[i][1]<self.min_heaps[j][1]:
                    n = self.min_heaps[i]
                    self.min_heaps[i] = self.min_heaps[j]
                    self.min_heaps[j] = n
                    i = j
                    continue
                if i%2==0 and self.min_heaps[i][1]<self.min_heaps[k][1]:
                    n = self.min_heaps[i]
                    self.min_heaps[i] = self.min_heaps[k]
                    self.min_heaps[k] = n
                    i = k
                    continue
                break


    def change_min(self,tup=None):
        list = self.min_heaps
        if tup==None:
            try:
                list[0] = list.pop()
            except IndexError:
                pass
        else:
            list[0] = tup
        # print(list)
        i = 0
        while (2 * i + 2) <= len(list):
            # 防止最后一个树节点为单个
            try:
                if list[2 * i + 1][1] < list[2 * i + 2][1]:
                    m = 2 * i + 1
                else:
                    m = 2 * i + 2
            except IndexError:
                m = 2 * i + 1

            if list[i][1] > list[m][1]:
                k = list[m]
                list[m] = list[i]
                list[i] = k
                i = m
            else:
                break

if __name__ == '__main__':
    '主函数'

    # k个有序数组合并成一个有序数组，总数量为n,使用堆排序可以将时间复杂度缩减到O(nlogk),当k较大时会比较有优势，但是我这个代码明显不优美高效，有待改进
    list1 = [5,6,9,12,22]
    list2 = [3,8,10,14,25]
    list3 = [8,9,24,30]
    list4 = [1,7,11,23,31,33]
    list5 = [4,5,9,12,22,43]
    all_list = []
    tup=()

    list = [('list1',list1.pop(0)),('list2',list2.pop(0)),('list3',list3.pop(0)),('list4',list4.pop(0)),('list5',list5.pop(0))]
    heap = Heap()
    heap.add_minheap(list)

    while(len(heap.min_heaps)>0):
        all_list.append(heap.min_heaps[0][1])
        try:
            if heap.min_heaps[0][0] == 'list1':
                tup = ('list1',list1.pop(0))
            elif heap.min_heaps[0][0] == 'list2':
                tup = ('list2', list2.pop(0))
            elif heap.min_heaps[0][0] == 'list3':
                tup = ('list3', list3.pop(0))
            elif heap.min_heaps[0][0] == 'list4':
                tup = ('list4', list4.pop(0))
            elif heap.min_heaps[0][0] == 'list5':
                tup = ('list5', list5.pop(0))
            heap.change_min(tup)
        except IndexError:
            heap.change_min()
    print(all_list)

堆排序 排序