Review: Heap Problems

heap is a specialized tree-based data structure. Heap is useful to implement a priority queue.

Key operations: find-min, get-min, insert, etc.



Code Skeleton

type MyNode struct {
    val int
    cnt int
}

// min heap
type IntHeap []MyNode
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i].cnt < h[j].cnt }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
        // Push and Pop use pointer receivers because they modify the slice's length,
        // not just its contents.
        *h = append(*h, x.(MyNode))
}

func (h *IntHeap) Pop() interface{} {
        old := *h
        n := len(old)
        x := old[n-1]
        *h = old[0 : n-1]
        return x
}

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

Complexity:

  1. Insert an element to binary heap. Time O(log(n))
  2. Remove the top from binary heap. Time O(log(n))
  3. Remove an item by value. Time O(n)
## 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.

linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.