Heap Basics¶
Table of Contents¶
- 1046. Last Stone Weight (Easy)
- 3264. Final Array State After K Multiplication Operations I (Easy)
- 2558. Take Gifts From the Richest Pile (Easy)
- 2336. Smallest Number in Infinite Set (Medium)
- 2530. Maximal Score After Applying K Operations (Medium)
- 3066. Minimum Operations to Exceed Threshold Value II (Medium)
- 1962. Remove Stones to Minimize the Total (Medium)
- 703. Kth Largest Element in a Stream (Easy)
- 3275. K-th Nearest Obstacle Queries (Medium)
- 2208. Minimum Operations to Halve Array Sum (Medium)
- 2233. Maximum Product After K Increments (Medium)
- 3296. Minimum Number of Seconds to Make Mountain Height Zero (Medium)
- 1942. The Number of the Smallest Unoccupied Chair (Medium)
- 1801. Number of Orders in the Backlog (Medium)
- 2406. Divide Intervals Into Minimum Number of Groups (Medium)
- 2462. Total Cost to Hire K Workers (Medium)
- 1834. Single-Threaded CPU (Medium)
- 3408. Design Task Manager (Medium)
- 1792. Maximum Average Pass Ratio (Medium)
- 2931. Maximum Spending After Buying Items (Hard)
- 1882. Process Tasks Using Servers (Medium)
- 2402. Meeting Rooms III (Hard)
- 253. Meeting Rooms II (Medium) 👑
- 1167. Minimum Cost to Connect Sticks (Medium) 👑
1046. Last Stone Weight¶
-
LeetCode | LeetCode CH (Easy)
-
Tags: array, heap priority queue
- Heap
- Time: O(n log n); Space: O(n)
- 0/1 Knapsack
- Time: O(n); Space: O(n)
from heapq import heapify, heappop, heappush
from typing import List
# Heap
def lastStoneWeightHeap(stones: List[int]) -> int:
maxHeap = [-s for s in stones]
heapify(maxHeap)
while len(maxHeap) > 1:
s1 = heappop(maxHeap)
s2 = heappop(maxHeap)
if s1 != s2:
heappush(maxHeap, s1 - s2)
return -maxHeap[0] if maxHeap else 0
# 0/1 Knapsack
def lastStoneWeightKnapsack(stones: List[int]) -> int:
total = sum(stones)
target = total // 2
dp = [0 for _ in range(target + 1)]
for i in stones:
for j in range(target, i - 1, -1):
dp[j] = max(dp[j], dp[j - i] + i)
return total - 2 * dp[target]
if __name__ == "__main__":
stones = [2, 7, 4, 1, 8, 1]
assert lastStoneWeightHeap(stones) == 1
assert lastStoneWeightKnapsack(stones) == 1
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int lastStoneWeight(vector<int> &stones)
{
priority_queue<int> maxHeap(stones.begin(), stones.end());
while (maxHeap.size() >= 1)
{
int first = maxHeap.top();
maxHeap.pop();
int second = maxHeap.top();
maxHeap.pop();
if (first != second)
{
maxHeap.push(first - second);
}
}
return maxHeap.empty() ? 0 : maxHeap.top();
}
int main()
{
vector<int> stones = {2, 7, 4, 1, 8, 1};
cout << lastStoneWeight(stones) << endl; // 1
return 0;
}
3264. Final Array State After K Multiplication Operations I¶
-
LeetCode | LeetCode CH (Easy)
-
Tags: array, math, heap priority queue, simulation
import heapq
from typing import List
# Brute Force
def getFinalStateBF(nums: List[int], k: int, multiplier: int) -> List[int]:
for _ in range(k):
minNum = min(nums)
idx = nums.index(minNum)
nums[idx] *= multiplier
return nums
# Heap
def getFinalStateHeap(nums: List[int], k: int, multiplier: int) -> List[int]:
minHeap = []
for idx, num in enumerate(nums):
heapq.heappush(minHeap, (num, idx))
for _ in range(k):
num, idx = heapq.heappop(minHeap)
nums[idx] = num * multiplier
heapq.heappush(minHeap, (nums[idx], idx))
return nums
k = 5
multiplier = 2
print(getFinalStateBF([2, 1, 3, 5, 6], k, multiplier)) # [8, 4, 6, 5, 6]
print(getFinalStateHeap([2, 1, 3, 5, 6], k, multiplier)) # [8, 4, 6, 5, 6]
2558. Take Gifts From the Richest Pile¶
-
LeetCode | LeetCode CH (Easy)
-
Tags: array, heap priority queue, simulation
from heapq import heapify, heappop, heappush
from math import isqrt
from typing import List
# Heap
def pickGifts(gifts: List[int], k: int) -> int:
maxHeap = [-g for g in gifts]
heapify(maxHeap)
for _ in range(k):
cur = heappop(maxHeap)
if cur == -1:
heappush(maxHeap, cur)
break
heappush(maxHeap, -isqrt(-cur))
return sum(-i for i in maxHeap)
if __name__ == "__main__":
assert pickGifts([25, 64, 9, 4, 100], 4) == 29
assert pickGifts([1, 1, 1, 1], 4) == 0
2336. Smallest Number in Infinite Set¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: hash table, design, heap priority queue, ordered set
from heapq import heappop, heappush
# Heap
class SmallestInfiniteSet:
def __init__(self):
self.cur_min = 1
self.added = set()
self.min_heap = []
def popSmallest(self) -> int:
if self.min_heap:
res = heappop(self.min_heap)
self.added.remove(res)
return res
res = self.cur_min
self.cur_min += 1
return res
def addBack(self, num: int) -> None:
if num < self.cur_min and num not in self.added:
self.added.add(num)
heappush(self.min_heap, num)
if __name__ == "__main__":
sis = SmallestInfiniteSet()
assert sis.popSmallest() == 1
sis.addBack(2)
assert sis.popSmallest() == 2
assert sis.popSmallest() == 3
sis.addBack(1)
assert sis.popSmallest() == 1
assert sis.popSmallest() == 4
sis.addBack(3)
assert sis.popSmallest() == 3
2530. Maximal Score After Applying K Operations¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, greedy, heap priority queue
from heapq import heapify, heappop, heappush
from math import ceil
from typing import List
# Heap
def maxKelements(nums: List[int], k: int) -> int:
res = 0
maxHeap = [-n for n in nums]
heapify(maxHeap)
while k > 0:
cur = -heappop(maxHeap)
res += cur
heappush(maxHeap, -ceil(cur / 3))
k -= 1
return res
if __name__ == "__main__":
assert maxKelements([10, 10, 10, 10, 10], 5) == 50
assert maxKelements([1, 10, 3, 3, 3], 3) == 17
assert maxKelements([1, 2, 3, 4, 5], 5) == 16
3066. Minimum Operations to Exceed Threshold Value II¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, heap priority queue, simulation
from heapq import heapify, heappop, heappush
from typing import List
# Heap
def minOperations(nums: List[int], k: int) -> int:
heapify(nums)
res = 0
while nums[0] < k:
x = heappop(nums)
y = heappop(nums)
heappush(nums, x * 2 + y)
res += 1
return res
if __name__ == "__main__":
assert minOperations([2, 11, 10, 1, 3], 10) == 2
assert minOperations([1, 1, 2, 4, 9], 20) == 4
1962. Remove Stones to Minimize the Total¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, greedy, heap priority queue
from heapq import heapify, heapreplace
from typing import List
# Heap
def minStoneSum(piles: List[int], k: int) -> int:
maxHeap = [-p for p in piles]
heapify(maxHeap)
for _ in range(k):
heapreplace(maxHeap, maxHeap[0] // 2)
return -sum(maxHeap)
if __name__ == "__main__":
assert minStoneSum([5, 4, 9], 2) == 12
assert minStoneSum([4, 3, 6, 7], 3) == 12
703. Kth Largest Element in a Stream¶
-
LeetCode | LeetCode CH (Easy)
-
Tags: tree, design, binary search tree, heap priority queue, binary tree, data stream
import heapq
from typing import List
# Heap
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.heap = []
for num in nums:
self.add(num)
def add(self, val: int) -> int:
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap)
return self.heap[0]
obj = KthLargest(3, [4, 5, 8, 2])
print(obj.add(3)) # 4
print(obj.add(5)) # 5
print(obj.add(10)) # 5
3275. K-th Nearest Obstacle Queries¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, heap priority queue
from heapq import heappop, heappush
from typing import List
# Heap
def resultsArray(queries: List[List[int]], k: int) -> List[int]:
n = len(queries)
res = [-1 for _ in range(n)]
maxHeap = []
for i in range(n):
dist = abs(queries[i][0]) + abs(queries[i][1])
heappush(maxHeap, -dist)
if i < k - 1:
continue
while len(maxHeap) > k:
heappop(maxHeap)
res[i] = -maxHeap[0]
return res
if __name__ == "__main__":
queries = [[1, 2], [3, 4], [2, 3], [-3, 0]]
k = 2
assert resultsArray(queries, k) == [-1, 7, 5, 3]
2208. Minimum Operations to Halve Array Sum¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, greedy, heap priority queue
2233. Maximum Product After K Increments¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, greedy, heap priority queue
3296. Minimum Number of Seconds to Make Mountain Height Zero¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, math, binary search, greedy, heap priority queue
from bisect import bisect_left
from heapq import heapify, heapreplace
from math import isqrt
from typing import List
# Min Heap
def minNumberOfSecondsMinHeap(
mountainHeight: int, workerTimes: List[int]
) -> int:
minHeap = [(t, t, t) for t in workerTimes]
heapify(minHeap)
for _ in range(mountainHeight):
nxt, delta, base = minHeap[0]
heapreplace(
minHeap,
(
nxt + delta + base,
delta + base,
base,
),
)
return nxt
# Binary Search Min Answer
def minNumberOfSecondsBinarySearchMin(
mountainHeight: int, workerTimes: List[int]
) -> int:
def check(m: int) -> bool:
left_h = mountainHeight
for t in workerTimes:
left_h -= (isqrt(m // t * 8 + 1) - 1) // 2
if left_h <= 0:
return True
return False
max_t = max(workerTimes)
h = (mountainHeight - 1) // len(workerTimes) + 1
return bisect_left(range(max_t * h * (h + 1) // 2), True, 1, key=check)
if __name__ == "__main__":
mountainHeight = 4
workerTimes = [2, 1, 1]
assert minNumberOfSecondsMinHeap(mountainHeight, workerTimes) == 3
assert minNumberOfSecondsBinarySearchMin(mountainHeight, workerTimes) == 3
1942. The Number of the Smallest Unoccupied Chair¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, hash table, heap priority queue
1801. Number of Orders in the Backlog¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, heap priority queue, simulation
2406. Divide Intervals Into Minimum Number of Groups¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, two pointers, greedy, sorting, heap priority queue, prefix sum
2462. Total Cost to Hire K Workers¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, two pointers, heap priority queue, simulation
1834. Single-Threaded CPU¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, sorting, heap priority queue
3408. Design Task Manager¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: hash table, design, heap priority queue, ordered set
1792. Maximum Average Pass Ratio¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, greedy, heap priority queue
2931. Maximum Spending After Buying Items¶
-
LeetCode | LeetCode CH (Hard)
-
Tags: array, greedy, sorting, heap priority queue, matrix
1882. Process Tasks Using Servers¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, heap priority queue
2402. Meeting Rooms III¶
-
LeetCode | LeetCode CH (Hard)
-
Tags: array, hash table, sorting, heap priority queue, simulation
253. Meeting Rooms II¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, two pointers, greedy, sorting, heap priority queue, prefix sum
- Given an array of meeting time
intervals
whereintervals[i] = [start_i, end_i]
, return the minimum number of conference rooms required.
import heapq
from typing import List
# Heap
def minMeetingRooms(intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[0])
minHeap = [intervals[0][1]]
for i in range(1, len(intervals)):
if intervals[i][0] >= minHeap[0]:
heapq.heappop(minHeap)
heapq.heappush(minHeap, intervals[i][1])
return len(minHeap)
if __name__ == "__main__":
intervals = [[0, 30], [5, 10], [15, 20]]
assert minMeetingRooms(intervals) == 2
1167. Minimum Cost to Connect Sticks¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, greedy, heap priority queue