1、最大堆/最小堆结构
（1）最大堆
堆顶元素最大，其他元素都小于等于：堆顶
（2）最小堆
堆顶元素最小，其他元素都大于等于：堆顶
常用函数：
python自带的建堆函数是最小堆
heap,heapify
经典例题：
1、数据流的第K大个元素
第K大用最小堆，返回的是第K大个元素
代码如下：
from heapq import *
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.que = nums
heapify(self.que)
#while len(self.nums)>self.k: #cut heap to size:k
#heappop(self.nums)
def add(self, val):
"""
:type val: int
:rtype: int
"""
heapq.heappush(self.que, val)
while len(self.que) > self.k:
heapq.heappop(self.que)
return self.que[0]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
2、多路归并
利用最小堆，完成有序序列的归并排序，666，还得看。。。。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
import heapq
d=ListNode(0)
p=d
head=[]
for i in range(len(lists)):
if lists[i] :
heapq.heappush(head,(lists[i].val,i))
lists[i]=lists[i].next
while head:
val,i=heapq.heappop(head)
p.next=ListNode(val)
p=p.next
if lists[i]:
heapq.heappush(head,(lists[i].val,i))
lists[i]=lists[i].next
return d.next
(2)不断的两路归并到K路！！！
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
#merge两个有序链表
def merge(s,t):
r=ListNode(0)
p=r
if not s and not t:
return
if not s :
return t
if not t:
return s
while s and t:
if s.val<t.val:
r.next=s
s=s.next
else:
r.next=t
t=t.next
r=r.next
if not s:
r.next=t
if not t:
r.next=s
return p.next
l=[]
k=len(lists)
print(k)
if k==0:
return
if k==1:
return lists[0]
for i in range(k-1):
l=merge(lists[i],lists[i+1])
lists[i+1]=l
return l
网友评论