A heap is a special Tree-based data structure in which the tree is a complete Binary Tree in which each level has all of its nodes. A complete binary tree is a tree in which each node can have a max of two children, and all the levels should be filled except for the last level, where nodes should be filled from left to right.
Min Heap: The value at each node should be smaller than its children.
Max Heap: The value at each node should be greater than its children.
We can implement a heap as an array.
def get_left_child(i):
return 2 * i + 1
def get_right_child(i):
return 2 * i + 2
def min_heapify(arr, i):
left = get_left_child(i)
right = get_right_child(i)
smallest = i
if left < len(arr) and arr[i] > arr[left]:
smallest = left
if right < len(arr) and arr[smallest] > arr[right]:
smallest = right
if smallest != i:
arr[i], arr[smallest] = arr[smallest], arr[i]
min_heapify(arr, smallest)
def build_min_heap(arr):
for i in reversed(range(len(arr)//2)):
min_heapify(arr, i)
def max_heapify(arr, i):
left = get_left_child(i)
right = get_right_child(i)
largest = i
if left < len(arr) and arr[left] > arr[largest]:
largest = left
if right < len(arr) and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
max_heapify(arr, largest)
Operation | Average | Worst Case | Best Case |
Search | O(n) | O(n) | O(1) |
Insert | O(1) | O(log n) | O(1) |
Delete | O(log n) | O(log n) | O(1) |
Peek | O(1) | O(1) | O(1) |
A heap tree can be used for many different purposes, including the following:
In Python, it is available using the “heapq” module. The property of this data structure in Python is that each time the smallest heap element is popped(min-heap). The heap[0] element also returns the smallest element each time.
Below is a list of these functions.
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.
arr = [2,3,4]
, the median is 3
.arr = [2,3]
, the median is (2 + 3) / 2 = 2.5
.Implement the MedianFinder class:
MedianFinder()
initializes the MedianFinder
object.void addNum(int num)
adds the integer num
from the data stream to the data structure.double findMedian()
returns the median of all elements so far. Answers within 10-5
of the actual answer will be accepted.To be able to solve these kinds of problems, we want to know the smallest element in one part and the biggest element in the other part. Two Heaps pattern uses two Heap data structure to solve these problems; a Min heap to find the smallest element and a Max Heap to find the biggest element.
Solution:
from heapq import heappush, heappop
class MedianFinder:
def __init__(self):
self.max_heap = []
self.min_heap = []
def addNum(self, num: int) -> None:
if not self.max_heap or -self.max_heap[0] >= num:
heappush(self.max_heap, -num)
else:
heappush(self.min_heap, num)
if len(self.max_heap) > len(self.min_heap) + 1:
heappush(self.min_heap, -heappop(self.max_heap))
elif len(self.max_heap) < len(self.min_heap):
heappush(self.max_heap, -heappop(self.min_heap))
def findMedian(self) -> float:
if len(self.max_heap) == len(self.min_heap):
return (-self.max_heap[0] + self.min_heap[0] )/ 2.0
return -float(self.max_heap[0])
Time Complexity: O(log N) for addNum()
and O(1) for findMedian()
. Space Complexity: O(N)
Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k
distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k
distinct projects.
You are given n
projects where the ith
project has a pure profit profits[i]
and a minimum capital of capital[i]
is needed to start it.
Initially, you have w
capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.
Pick a list of at most k
distinct projects from given projects to maximize your final capital, and return the final maximized capital.
The answer is guaranteed to fit in a 32-bit signed integer.
Solution:
import heapq
class Solution:
def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
heap = []
for c,p in zip(capital, profits):
heapq.heappush(heap, (c,-p))
do_list = []
for i in range(k):
while heap and heap[0][0] <= w:
c,p = heapq.heappop(heap)
heapq.heappush(do_list, (p,c))
if do_list:
p,c = heapq.heappop(do_list)
w += -1 * p
return w