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

See all heap problems: #heap

Useful Link:

See more blog posts.

Post Views: 8