# 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
heapq.heappop(l)
heapq.heapify(l)
return True
return False
```

See all heap problems: #heap

Useful Link:

See more blog_posts.

Share It, If You Like It.