Review: Heap Problems

Posted on January 22, 2018September 3, 2019 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
Questions

Name	Example

Code Skeleton

// 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
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