Review: Heap Problems Posted on January 22, 2018July 26, 2020 by braindenny heap is a specialized tree-based data structure. Heap is useful to implement a priority queue. Key operations: find-min, get-min, insert, etc. Basic Abstractions Name Summary Build a heap Time O(n) Insert an element to binary heap Time O(log(n)) Remove the top from binary heap Time O(log(n)) Remove an item by value Time O(n) For topk max, need minheap, instead of maxheap Scenarios Code Skeleton Top Questions Num Problem Summary 1 Meeting Rooms II LeetCode: Meeting Rooms II 2 Task Scheduler LeetCode: Task Scheduler 3 Last Stone Weight LeetCode: Last Stone Weight 4 The Skyline Problem LeetCode: The Skyline Problem 5 Task Scheduler LeetCode: Task Scheduler Code Skeleton ## https://code.dennyzhang.com/merge-k-sorted-lists ## Basic Ideas: heap ## ## Complexity: Time O(n*log(k)), Space O(1) # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None import heapq class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: l = [] # minheap for i in range(len(lists)): node = lists[i] if node: heapq.heappush(l, (node.val, id(node), node)) dummyHead = ListNode(0) p = dummyHead # heapq.heapify(l) while len(l)>0: (_, _, q) = heapq.heappop(l) if q.next: heapq.heappush(l, (q.next.val, id(q.next), q.next)) p.next = q p = p.next # close the linked list p.next = None return dummyHead.next // Blog link: https://code.dennyzhang.com/minimum-cost-to-connect-sticks // Basic Ideas: min heap // cost = (n-1)*l[0]+(n-1)*l[1]+(n-2)*l[2]+(n-3)*l[3]....+ l[n-1] // Complexity: O(n*log(n)), Space O(1) // min heap import "container/heap" type IntHeap []int func (h IntHeap) Len() int { return len(h) } func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) } func (h *IntHeap) Pop() interface{} { res := (*h)[len(*h)-1] *h = (*h)[0:len(*h)-1] return res } func connectSticks(sticks []int) int { h := &IntHeap{} heap.Init(h) for _, v := range sticks { heap.Push(h, v) } res := 0 for h.Len() != 1 { n1 := heap.Pop(h).(int) n2 := heap.Pop(h).(int) res += n1+n2 heap.Push(h, n1+n2) } return res } Ideas Name Example Min heap or max heap? Check the root of the heap Binary heaps: It may be represented by using an array, which is space-efficient. The children of the node at position n would be at positions 2n + 1 and 2n + 2 in a zero-based array. From child to parent: n -> (n-1)/2 ## Blog link: https://code.dennyzhang.com/sliding-window-median def heapRemove(self, l, item): k = -1 for i in range(len(l)): if l[i] == item: k = i break if k != -1: l[k] = l[0] heapq.heappop(l) heapq.heapify(l) return True return False CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups See all heap problems: #heap Review: Heap ProblemsLintCode: Second Max of ArrayLintCode: Number of restaurantsLeetCode: Trapping Rain Water IILeetCode: Top K Frequent WordsLeetCode: Top K Frequent ElementsLeetCode: Third Maximum NumberLeetCode: The Skyline ProblemLeetCode: The Maze IIILeetCode: Task SchedulerLeetCode: Super Ugly NumberLeetCode: Sort Characters By FrequencyLeetCode: Sliding Window MedianLeetCode: Network Delay TimeLeetCode: Minimum Cost to Connect SticksLeetCode: Merge k Sorted ListsLeetCode: Meeting Rooms IILeetCode: Maximum Number of Events That Can Be AttendedLeetCode: Last Stone WeightLeetCode: Kth Smallest Element in a Sorted MatrixLeetCode: Kth Largest Element in an ArrayLeetCode: Kth Largest Element in a StreamLeetCode: K Closest Points to OriginLeetCode: Find Smallest Common Element in All RowsLeetCode: Find K Pairs with Smallest SumsLeetCode: Employee Free TimeLeetCode: Design TwitterLeetCode: Design A LeaderboardLeetCode: Construct Target Array With Multiple SumsLeetCode: Constrained Subset Sum Useful Link: Heap queue (or heapq) in Python How to use Queue: A beginner’s guide See more blog posts. Post Views: 8