Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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:

  1. It may be represented by using an array, which is space-efficient.
  2. The children of the node at position n would be at positions 2n + 1 and 2n + 2 in a zero-based array.
  3. 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 Problems
  • LintCode: Second Max of Array
  • LintCode: Number of restaurants
  • LeetCode: Trapping Rain Water II
  • LeetCode: Top K Frequent Words
  • LeetCode: Top K Frequent Elements
  • LeetCode: Third Maximum Number
  • LeetCode: The Skyline Problem
  • LeetCode: The Maze III
  • LeetCode: Task Scheduler
  • LeetCode: Super Ugly Number
  • LeetCode: Sort Characters By Frequency
  • LeetCode: Sliding Window Median
  • LeetCode: Network Delay Time
  • LeetCode: Minimum Cost to Connect Sticks
  • LeetCode: Merge k Sorted Lists
  • LeetCode: Meeting Rooms II
  • LeetCode: Maximum Number of Events That Can Be Attended
  • LeetCode: Last Stone Weight
  • LeetCode: Kth Smallest Element in a Sorted Matrix
  • LeetCode: Kth Largest Element in an Array
  • LeetCode: Kth Largest Element in a Stream
  • LeetCode: K Closest Points to Origin
  • LeetCode: Find Smallest Common Element in All Rows
  • LeetCode: Find K Pairs with Smallest Sums
  • LeetCode: Employee Free Time
  • LeetCode: Design Twitter
  • LeetCode: Design A Leaderboard
  • LeetCode: Construct Target Array With Multiple Sums
  • LeetCode: Constrained Subset Sum

Useful Link:

  • Heap queue (or heapq) in Python
  • How to use Queue: A beginner’s guide

See more blog posts.

linkedin
github
slack

Post Views: 8
Posted in ReviewTagged #heap, review

Post navigation

LeetCode: Number of Islands
Review: Graph Problems

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.