【Python】堆之合并链表

23. 合并K个升序链表

https://leetcode.cn/problems/merge-k-sorted-lists/

思路：

• 考虑边界条件，lists为[]、[[]]、[[], []]的情况
• 遍历，获取所有的数放入列表
• 排序，初始化头指针和辅助指针，再遍历形成链表
• 返回头指针

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
            
        li = []
        for link_list in lists:  # 把所有的数放入列表
            while link_list:
                li.append(link_list.val)
                link_list = link_list.next
        if not li:
            return None

        li.sort()
        cur = head = ListNode(val=li[0])
        li = li[1:]
        while li:
            new_node = ListNode(li[0])
            cur.next = new_node
            cur = new_node
            li = li[1:]
        return head

只打败了26%的人？？？哪里出了问题

不对啊，需要排序，为什么我要排序后再遍历？我就不可以遍历的同时排序吗。

PS： max、min这种的函数无法做到删除操作，所以，采用堆进行排序

最小堆优化版本：

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        import heapq
        if not lists:
            return None
            
        li = []
        for link_list in lists:  # 把所有的数放入列表
            while link_list:
                li.append(link_list.val)
                link_list = link_list.next
        if not li:
            return None

        heapq.heapify(li)  # 建堆
        cur = head = ListNode(val=heapq.heappop(li))
        while li:
            new_node = ListNode(val=heapq.heappop(li))
            cur.next = new_node
            cur = new_node
        return head

堆的知识补充：

堆是完全二叉树，完全二叉树的定义自行百度

堆有特性：向下（上）调整，即所有的根父节点 > 孩子节点。因此根节点为最大的数

堆排序的特性：堆排序是交换排序，不打乱原有位置，比较稳定。时间复杂度O(nlogn)

# 对于堆的向下调整（向上调整）
def sift(li, low, high):
    """
    low: 当前根节点
    high: 堆最后一个节点
    """
    tmp = li[low]  # 存根节点
    i = low
    j = 2 * i + 1  # 先指向左节点
    while j <= high:
        if j + 1 <= high and li[j+1] > li[j]:  # 右节点存在且大于左节点，j指向右节点
            j += 1
        if li[j] > tmp:  # 孩子大于父节点，孩子上位
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            # 孩子不能上位，tmp补上
            break
    li[i] = tmp  # 到叶子节点的时候，tmp进空位

# 对于堆的建立
from random import randint
li = [randint(1, 100) for _ in range(10)]
print(f"初始列表:{li}")
for i in range((len(li)-2)// 2, -1, -1):
    sift(li, i, len(li)-1)
print(f"建立的堆：{li}")
# 堆建立只保证 根父节点 > 孩子节点，根节点为最大的
# 对于堆排序，把最大的换到后面去，其余的数进行堆的向下调整
for j in range(len(li)-1, -1, -1):
    li[0], li[j] = li[j], li[0]
    sift(li, 0, j-1)
print(f"排序后的堆:{li}")

Python内置函数

import heapq
ls = [6,4,5,4,3,2,1,1]
heapq.heapify(ls)  # 建堆
print(ls)
# for i in range(len(ls)-1, -1, -1):
    # ls[i], ls[0] = ls[0], ls[i]
    
# heapq.heappop(ls)  # 获得堆最小值
# heapq.heappush(ls, 8)  # 加入堆

# heapq.heappushpop(ls, 8)  # 获得堆最小值，同时将一个数加入堆，有返回值
# heappushpop先push后pop，空堆不报错

# heapq.heapreplace(ls, 9)  # 获得堆最小值，同时将一个数加入堆，有返回值
# heapreplace先pop后push，表现为空堆报错
print(ls)