1、最大堆/最小堆結(jié)構(gòu)
（1）最大堆
堆頂元素最大，其他元素都小于等于：堆頂
（2）最小堆
堆頂元素最小，其他元素都大于等于：堆頂
常用函數(shù)：
python自帶的建堆函數(shù)是最小堆
經(jīng)典例題：
1、數(shù)據(jù)流的第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路?。。?/p>
代碼如下：
#?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
