Heap
Heap
is data structure organized by a binary tree in which the value of a parent node is greater than its children (max heap
).Heap
in Python is implemented with the heapq
module including the following functionalities
heapq.heappush(heap, item)
: push an item into heapheapq.heappop(heap)
: pop an item from heapheapq.pushpop(heap, item)
: push an item into heap and pop an item from heapheapq.heapify(list)
: transform a list into heapheapq.heapreplace(heap, tiem)
: pop an item from heap and push an new item from heapheap
Time Complexity compare to other data structures
Structure | Insertion | Deletion of Min | Remove | findMin | sort |
---|---|---|---|---|---|
heap |
O(logN) | O(logN) | O(logN) | O(1) | O(NlogN) |
orderedarray |
O(N) | O(1) | O(1) | O(N) | O(N) |
unordered array |
O(1) | O(N) | O(1) | O(N) | O(NlogN) |
BST |
O(logN) | O(logN) | O(logN) | O(logN) | O(N) |
heap
and internal sort is given as the following
class Solution:
# @param {integer[]} nums
# @param {integer} k
# @return {integer}
def findKthLargest(self, nums, k):
'''
'''
#return solution_sort(nums,k)
return solution_heap(nums,k)
import heapq
def solution_heap(nums,k):
h = []
for num in nums:
h.append(-num)
heapq.heapify(h)
print h
res = []
for i in xrange(k):
res = (heapq.heappop(h))
print res
return -res
pass
def solution_sort(nums,k):
'''
use build-in sort
'''
if len(nums) == 0: return None
nums.sort()
return nums[len(nums)-k]
pass
heap
approach: add element into a heap one by another, in each step
deque
structuredeque
is empty, add current number into the head of deque
class Solution:
# @param {integer[]} nums
# @param {integer} k
# @return {integer[]}
def maxSlidingWindow(self, nums, k):
return solution(nums,k)
def solution(nums,k):
'''
29
'''
if len(nums) == 0: return nums
h = []
res = []
for i in xrange(k):
heapq.heappush( h, (-nums[i],i) )
(val,i) = heapq.heappop(h)
res.append(-val)
heapq.heappush( h, (-nums[i],i) )
print res
for j in xrange(k,len(nums)):
heapq.heappush( h, (-nums[j],j) )
(val,i) = heapq.heappop(h)
while i<j-k+1:
(val,i) = heapq.heappop(h)
res.append(-val)
heapq.heappush( h,(-nums[i],i) )
return res
heap
with $k$ elements, and in each step
heap
heap
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param {ListNode[]} lists
# @return {ListNode}
def mergeKLists(self, lists):
return solution(lists)
def solution(lists):
if len(lists) == 0: return None
if len(lists) == 1: return lists[0]
res = []
h = []
for i in xrange(len(lists)):
if lists[i] != None:
heapq.heappush(h, (lists[i].val,i) )
lists[i] = lists[i].next
while len(h)>0:
(val,i) = heapq.heappop(h)
res.append(val)
if lists[i] != None:
heapq.heappush(h, (lists[i].val,i))
lists[i] = lists[i].next
if len(res) == 0: return None
print res
head = ListNode(res[0])
p = head
for i in xrange(1,len(res)):
tmp = ListNode(res[i])
p.next = tmp
p=p.next
return head
heap
structure in O(nlogn) time where n is the number of buildings from the input.heap
of buildings and in each iteration
heap
heap
.class Solution:
# @param {integer[][]} buildings
# @return {integer[][]}
def getSkyline(self, buildings):
if len(buildings) == 0: return []
res = []
heap = []
activebuilding = ( buildings[0][2],buildings[0][0],buildings[0][1] )
res.append( [activebuilding[1],activebuilding[0]] )
i=0
while i<len(buildings)-1:
i+=1
currentbuilding = (buildings[i][2],buildings[i][0],buildings[i][1])
if len(buildings) < 10: print i,heap,res,activebuilding,currentbuilding
if currentbuilding[1] > activebuilding[2]:
# current start on the right
# process current heap
if len(heap) == 0:
res.append( [activebuilding[2],0] )
activebuilding = currentbuilding
res.append( [activebuilding[1],activebuilding[0]] )
else:
while len(heap) > 0:
(a,b,c) = heapq.heappop(heap)
newactivebuilding = (-a,b,c)
if newactivebuilding[2] > activebuilding[2]:
break
if newactivebuilding == None:
res.append( [activebuilding[2],0] )
activebuilding = currentbuilding
res.append( [activebuilding[1],activebuilding[0]] )
else:
res.append( [activebuilding[2],newactivebuilding[0]] )
activebuilding = newactivebuilding
i-=1
elif currentbuilding[1] < activebuilding[2]:
# current start on the left
if currentbuilding[0]>activebuilding[0]:
heapq.heappush(heap,(-activebuilding[0],activebuilding[1],activebuilding[2]))
activebuilding = currentbuilding
print '--', activebuilding
res.append([activebuilding[1],activebuilding[0]])
else:
heapq.heappush(heap,(-currentbuilding[0],currentbuilding[1],currentbuilding[2]))
elif currentbuilding[1] == activebuilding[2]:
# current start on the same position
if currentbuilding[0] >= activebuilding[0]:
activebuilding = currentbuilding
else:
heapq.heappush(heap,(-currentbuilding[0],currentbuilding[1],currentbuilding[2]))
(a,b,c) = heapq.heappop(heap)
currentbuilding = (-a,b,c)
res.append([activebuilding[2],currentbuilding[0]])
activebuilding = currentbuilding
if len(buildings) < 10: print 'heap', heap,res
# no more element
if len(heap) == 0:
res.append( [activebuilding[2],0] )
while len(heap) > 0:
if len(buildings) < 10:print heap
(a,b,c) = heapq.heappop(heap)
currentbuilding = (-a,b,c)
while len(heap) >0 and currentbuilding[2] <= activebuilding[2]:
(a,b,c) = heapq.heappop(heap)
currentbuilding = (-a,b,c)
if currentbuilding[2] > activebuilding[2]:
res.append( [activebuilding[2],currentbuilding[0]] )
activebuilding = currentbuilding
res.append([activebuilding[2],0])
# process res
newres = []
for i in xrange(len(res)-1):
if res[i][0] != res[i+1][0]:
newres.append(res[i])
newres.append(res[len(res)-1])
print 'newres',newres
return newres